랜선 자르기 - 이진 탐색 (파이썬)

사이트 링크 : https://www.acmicpc.net/problem/1654

 

문제는 아래와 같습니다.

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

• 해당 사이트에 예제 입력이 있습니다.

문제 해결 포인트 

• 해당문제는 프로그래머스의 입국 심사 와 거의 푸는 방법이 동일한 문제입니다.
• 랜선을 만들수있는 최대 길이를 구하는 문제에서는  각 랜선이 만들수있는 값을 확인하기 위해 
• mid 로 나누어 count 를 한뒤 실제 필요한 n 보다 이상으면 answer로 값을 저장해두고 
• 이진 탐색을 진행하면 됩니다. 

정답코드 

k, n = map(int, input().split())
k_list = []
for _ in range(k):
    k_list.append(int(input()))

start = 1
end = max(k_list) * n
# end = 2**31 - 1  # 2^31 -1
answer = 0
while start <= end:
    mid = (start + end)//2
    count = 0
    for i in k_list:
        count += i//mid
        if count >= n:
            break
    if count >= n:
        start = mid + 1
        answer = mid
    else:
        end = mid-1

print(answer)

 

보통 이진 탐색으로 최대를 구할떄는 count 가 start 보다 높을때는 최적의 값을 저장하고 최소의 값을 구할떄는 end 가 움직일 조건에 최적의 값을 저장하는것 같습니다. (반드시는 아니고 문제에 상황에 잘 적용을 하시면 될것같습니다.)