[BOJ] 1654 - 랜선 자르기

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

1654번: 랜선 자르기

import sys
k, n = map(int, sys.stdin.readline().rstrip().split())

data = []
for i in range(k):
    data.append(int(sys.stdin.readline().rstrip()))

start = 1
end = max(data)

while start <= end:
    mid = (start + end) // 2
    cnt = 0
    for x in data:
        cnt += x // mid

    if cnt >= n:
        start = mid + 1

    else:
        end = mid - 1

print(end)

전형적인 이진 탐색 문제이자, 파라메트릭 서치 유형의 문제이다.

풀이방법은 랜선 개수 n을 채울 때까지 랜선의 길이를 계속해서 조정하는 것이다. 그래서 '현재 이 길이로 n개 이상의 랜선을 만들 수 있는 가?'를 확인한 뒤에 조건의 만족 여부 ('예' 혹은 '아니오')에 따라서 탐색 범위를 좁혀나가며 해결하는 것이다.

 

범위를 좁힐 때는 이진 탐색의 원리를 이용하여 절반씩 탐색 범위를 좁혀 나간다. 시작점을 1, 끝점을 랜선 중 가장 긴 길이로 두고 모든 랜선을 그 중간값인 mid로 나누어 총 몇 개의 랜선이 나오는지 확인한 후 랜선의 개수가 n 이상이면 mid의 오른쪽 범위, n 이하면 mid의 왼쪽 범위를 반복적으로 탐색한다.

 

start와 end가 같아지면 조건을 만족하는 최대 랜선길이를 구하는 것이 목적이므로 가장 큰 값인 end를 출력해야한다.

---

느낀 점

이진 탐색 알고리즘으로 이러한 유형의 문제를 풀 수 있다는 것이 신기했다.

문제에서 조건을 만족하는 가장 큰 값을 출력해야 하기 때문에 end를 출력해야했지만 이진 탐색 알고리즘의 원리를 계속해서 생각하다보니 mid를 출력하려고 했던 것이 큰 아쉬움이었다.