[백준] 1654번 - 랜선 자르기 (이분 탐색) - 결과 포함

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

앞선 문제들은 기본적인 이분 탐색 코드를 어느 정도 외우고 있으면 풀 수 있는 간단한 문제들이었다.

1654번: 랜선자르기 문제부터는 파라메트릭 서치 (Parametric Search) 유형의 문제들이 나왔다.

 

파라메트릭 서치란 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다.

범위 내의 가장 큰 값, 작은 값을 찾는 문제들이 주로 이 유형에 해당하며,

보통 코딩테스트에서는 이러한 파라메트릭 서치 유형을 이분 탐색을 이용해 해결한다고 한다.

 

범위를 절반으로 줄여나가면서 가장 최적의 값을 찾아 나가는 방식이 그리디와 흡사한 면이 존재한다.

 

이 문제를 요약하면 가지고 있는 랜선의 개수 K를 가지고 필요한 랜선 개수 N을 만들어 냈을 때 만들 수 있는 최대 길이를 찾는 문제이다.

 

먼저 답이 될 수 있는 범위를 정해보자

만약 가지고 있는 랜선이

100

200

300

400

800

이렇게 5개라면,

정답은 1 ~ 800 사이일 것이다.

가장 길이가 긴 랜선이 800인데 900이나 1000같은 길이를 만들 수는 없기 때문이다.

또한 가지고 있는 랜선이 1개이고 필요한 랜선도 1개라면 바로 가지고 있는 랜선의 길이가 최대 길이가 된다.

 

이제 범위를 정했으니 이분 탐색을 진행하면 된다.

파라메트릭 서치가 최적화에서 결정으로 바꾸어 해결한다고 했는데

이 문제에서는 만들 수 있는 최대 길이를 찾는 최적화 문제에서 x라는 길이로 랜선들을 모두 잘랐을 때 필요한 개수가 나오는 지를 판단하는 문제로 바꿀 수 있다.

 

최초에는 0과 최대 길이의 랜선의 중간값으로 모든 랜선들을 잘라본다.

저장되어 있는 랜선들을 현재 중간값으로 나눈 몫을 모두 더하면 필요한 갯수만큼 랜선이 나오는지 알 수 있다.

만약에 필요한 갯수보다 적게 나온다면 더 짧은 길이로 잘라야한다. 중간값 - 1을 상한선(end)로 바꾼다.

반대로 갯수보다 많이 나오거나 갯수와 동일하게 나온다면 중간값 + 1을 하한선(start)로 바꾼다.

 

이렇게 반복하다 보면 필요한 랜선만큼 얻을 수 있는 최대의 길이를 알 수 있다.

 

[소스코드]

import sys

k, n = map(int, sys.stdin.readline().rstrip().split(' '))
data = list()

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

start = 0
end = max(data)

result = 0
while start <= end:
    count = 0
    mid = (start + end) // 2
    if mid == 0:
        result = end
        break
    for l in data:
        count += l // mid
    if count < n:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

처음에 제출했을 때 런타임 오류가 떴는데

그 이유는 중간값(mid)가 0이 되는 경우가 있었기 때문이다.

만약 최대 길이의 랜선이 1인 경우 처음에 중간값이 0이 나온다.

이 중간값으로 1을 나누려고 하다보니 1 / 0 (zeroDivision) 에러가 발생했다.

 

기초적인 오류이지만 문제 해결에 집중하다 보니 놓쳤다.

다음부터 주의하도록 해야겠다.