엘리트 학원은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 선생님은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm 은 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자를때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수 길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.
결정 알고리즘을 몰라서 찾아보며 풀이를 시도하다가 실패했다.. 아래는 해설을 듣고 이해한 내용이다.
같은 길이 N개가 나와야 하는데 가지고 있던 K개 중 802 랜선이 가장 길다. 즉, N개 만들 수 있는 랜선의 최대 길이는 802를 넘지 않을 것이라는 것을 알 수 있다. 따라서 길이의 범위는 1~802가 된다.
넉넉히 1~1000 으로 잡고 풀어도 된다. 어차피 이 범위 사이에 답이 존재하기 때문이다. 여기서부터 이분탐색을 사용한다.
1~1000 사이의 500을 랜선 길이로 가정 했을 때, 이미 가지고 있는 K개의 랜선들에서 500씩 잘라서 N개가 되는지 확인한다. 500이 답이 되지 않으면 500 이상인 600, 700, .. 등은 당연히 답이 되지 않을 것이다. 따라서 500~1000 사이는 제외한다.
이제 1~499 사이에서 답을 찾아야 한다. 이제 250을 랜선 길이로 가정하고 답이 되는가를 확인한다. 이 과정을 반복하여 푸는 것이다.
하지만 여기서 만약 250을 랜선 길이로 가정했을 때 N개보다 큰 개수가 나왔다면 N개도 당연히 만들 수 있을 것이다. (예를 들어 N=10 인데 250 길이로 잘라보니 같은 길이 20개가 나왔다면 나머지 10개를 버림으로써 N이 10개 나왔다고 할 수 있는 것이다.) 즉, 250도 답이 되지만 최대 길이를 구해야 하므로 범위를 251~499로 범위를 재설정하면 된다.
최대 길이의 답을 구해야 한다는 것을 명심하자! 답이 될 수 있는 길이는 계속 나오겠지만 최대 길이가 될 수 있는 답은 마지막에 나올 것이다.
<모범답안>
def Count(len):
cnt = 0
for x in Line:
cnt += (x//len)
return cnt
k, n = map(int, input().split())
Line = []
res = 0
largest = 0
for _ in range(k):
tmp = int(input())
Line.append(tmp)
largest = max(largest, tmp)
lt = 1
rt = largest
while lt <= rt:
mid = (lt + rt) // 2 # mid는 계속 바뀌어야 하기 때문에 while문 안에 있어야함
if Count(mid) >= n: # 참이면 mid는 답이 될 수 있음
res = mid
lt = mid+1
else:
rt = mid-1
print(res)