백준 1654번 - 랜선 자르기

랜선 자르기 문제 바로 가기

풀이 날짜: 2026-01-22

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline

k,n = map(int, input().split())
data = list(int(input()) for _ in range(k))

start = 1
end = max(data)
answer = 0

while start <= end:
    mid = (start + end) // 2
    count = 0

    for i in data:
        count += i // mid

    if count >= n:
        answer = mid
        start = mid + 1
    else:
        end = mid - 1
print(answer)

문제 접근

랜선 길이를 x라고 할 때, x가 작을수록 더 많은 랜선을 만들 수 있고, x가 커질수록 만들 수 있는 개수는 줄어든다. 즉, 길이에 따라 가능/불가능이 단조롭게 변하는 구조를 가진다. 이런 형태는 전형적인 이분 탐색 적용 조건이다.

이분 탐색 대상과 범위 설정

이분 탐색 대상은 랜선을 자를 길이(mid)이다. 가장 짧은 길이는 1, 가장 긴 길이는 입력으로 주어진 랜선 중 최댓값이므로 탐색 범위는

시작 값(start) = 1
끝 값(end) = max(data)

mid 값의 의미 – “이 길이로 자를 수 있을까?”

다솜을 제외한 후보들의 득표 수를 힙에 저장할 때는 -x 형태로 넣는다. 이렇게 하면 최소 힙에서 가장 작은 값인 -x가 곧 원래 값 기준 최대 득표 후보가 된다.

heapq.heappush(heap, -x)

분기 조건의 핵심

이 문제에서 가장 중요한 분기 조건은 다음과 같다.

count >= n
- 현재 길이 mid는 가능
- 더 긴 길이도 가능한지 확인해야 하므로 오른쪽 구간을 탐색해야 한다.
count < n
- 현재 길이 mid는 너무 길다.
- 더 짧은 길이를 탐색해야 하므로 왼쪽 구간 탐색

여기서 중요한 점은 “가능한 길이 중 최댓값”을 찾는 문제라는 것이다. 따라서 count >= n인 경우에는 mid를 정답 후보로 저장한 뒤, 더 큰 값이 가능한지 탐색을 계속 해봐야 한다.

answer 변수를 사용하는 이유

count >= n인 경우의 mid는 정답이 될 수 있는 값이므로, 이를 바로 버리면 안 된다. 그래서 매번 가능한 mid를 만났을 때 answer = mid로 저장해 둔다. 이렇게 하면 탐색이 끝난 뒤에도 가능했던 값 중 가장 큰 값을 안전하게 출력할 수 있다.

Vienna sausage