[BaekJoon] 1654 랜선 자르기

[출처 : https://www.acmicpc.net/problem/1654]

 

k, n = map(int,input().split())

kLength = list()
result = list()

for i in range(k):
    kLength.append(int(input()))

kLength.sort()


def binarySearch(data, n2):
    low=1
    # 랜선의 길이는 자연수라고 명시되어있다..
    # 조심하자..
    # low를 0으로 해놓고 헛짓거리함..
    high = data[len(data)-1] + 1
    '''
     4 4
     100
     100
     100
     100
     과 같은 입력이 들어왔을때 high값도 탐색 범위에 포함시키기 위해 1더해주기.
    '''

    while (low <= high):
        # while 조건을 단순히 low 가 작은 경우로만 해주면 high와 low가 같은 경우의 값은 비교를 진행하지 않음
        # 이진탐색 조건을 잘 생각해보자. 그리고 가능한 low <= high 으로 사용해보자
        mid = (low + high) // 2
        total = 0
        for kl in data:
            total += kl // mid
       
        if total >= n2 :
            result.append(mid)
            low = mid + 1
        else:
            high = mid - 1

# mid 가 0인경우 생각해보기
binarySearch(kLength, n)

print(max(result))

 

문제풀이

 

1. 초기 입력문 처리

2. 각각의 랜선 길이는 kLength 리스트에 저장 => 그 후 정렬

3. 이진 탐색 함수 작성 => 각 중간값을 반복할때마다 그때 길이로 각각의 랜선에서 나올 수 있는 개수를 구하고 개수가 기준값보다 크거나 같은 경우는 low값을 올려 탐색하도록 구현 이때 조건에 맞는 기준값들은 result 리스트에 append

4. binarySearch() 함수 호출

5. 결과 출력