[Baekjoon 1654 / Python / 실버2] 랜선 자르기

문제

 

이분 탐색 문제이다. 늘 결과 도출 부분에서 묘하게 헷갈린다.

 

# 실버2 -> 이분 탐색

"""

K : 이미 가지고 있는 랜선의 개수

N : 만들어야 할 랜선의 개수

data[] : K개 랜선 리스트

start : 1 -> 랜선 최소 길이

end : max(data) -> 랜선 최대 길이

- 랜선 길이를 기준으로 이분 탐색 실시

- 반복할 때 마다 조건 검사

    -> 해당 길이로 N개 랜선 제작이 가능한지

    -> 모든 랜선을 일일이 길이로 나눠 총 랜선 개수 세기

- 최대값을 찾아야 하므로 end 출력

"""

import sys

input = sys.stdin.readline

K, N = map(int, input().split())

data = [int(input()) for _ in range(K)]

start = 1

end = max(data)

while start <= end:

    mid = (start + end) // 2

    count = 0

    for lan in data:

        count += lan // mid

   

    if count >= N:

        start = mid + 1

    else:

        end = mid - 1

print(end)

 

이분 탐색 알고리즘을 이용하면 된다.

"랜선 길이"를 기준으로 이분 탐색을 실시하며, 매 반복마다 총 랜선 개수를 계산하여 그 결과에 따라 start 또는 end를 옮겨준다. 총 랜선 개수를 계산하는 for문은, K가 최대 10000 밖에 안되기 때문에 크게 신경쓰지 않아도 된다.

start는 랜선의 최소 길이인 1로, end는 입력받은 K개의 랜선 중 가장 긴 값으로 할당한다.

 

일반적인 이분 탐색 문제에서의 조건은 while start <= end 로 하며,

최소값을 찾을 경우 start를

최대값을 찾을 경우 end를

정확한 값을 찾을 경우 mid를 출력하면 된다.

 

결과