이진 탐색(이분 탐색): 백준 1654 파이썬

문제:

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

정답: 

import sys

k, n = map(int, sys.stdin.readline().split())
array = [int(sys.stdin.readline()) for _ in range(k)]

# 이진 탐색을 위한 시작점과 끝점 설정
start = 1
end = max(array)

# 이진 탐색 수행(반복적)
result = 0
while(start <= end):
    total = 0
    # mid: 자를 랜선 길이 
    mid = (start + end) // 2
    for x in array:
        #  자른 랜선의 개수 저장
        total += x // mid
    # 랜선의 개수가 목표 n 보다 작을 경우 자르는 길이를 줄여 랜선의 개수를 늘림 (왼쪽 부분 탐색)
    if total < n:
        end = mid - 1
    # 랜선의 길이가 목표 n 보다 클 경우 자르는 길이를 늘려 랜선의 개수를 줄임(오른쪽 부분 탐색)
    else:
        result = mid
        start = mid + 1

print(result)

 

풀이:

 

자르는 랜선의 길이를 이진 탐색으로 찾는 방법으로 정답을 맞힐 수 있었다.