(파이썬) 백준 1654번 "랜선 자르기"

---

# 답

K, N = map(int, input().split())
lan = [int(input()) for _ in range(K)]

lo = 1
hi = max(lan)
mi = (lo + hi) // 2

while lo <= hi:
    tot = 0
    for i in lan:
        tot += i // mi

    if tot >= N:
        if lo == mi:
            lo += 1
        else:
            lo = mi
    elif tot < N:
        if hi == mi:
            hi -= 1
        else:
            hi = mi
    mi = (lo + hi) // 2

print(mi)

~~

 

 

 

 

---

# 풀이

 

 

파라메트릭 서치로 푸는 대표적인 문제입니다. 파라메트릭 서치는 이분 탐색과 거의 유사한 알고리즘인데요. 차이점은, 이분 탐색은 탐색범위를 좁혀나가다가 정답을 발견하면 바로 함수를 빠져나오는 반면, 파라메트릭 서치는 더 이상 살펴볼 것이 없을 때까지 함수를 종료하지 않습니다. 이분 탐색과 파라메트릭 서치가 더 궁금하시다면 아래 포스팅을 확인해주세요.

(파이썬) 알고리즘 유형 5. 이분 탐색

 

이 문제에서 정답이 될 수 있는 랜선의 길이는 최소는 1이고 최대는 가장 긴 랜선의 길이입니다. 정답이 될 수 있는 범위(최솟값, 최댓값)를 알고 있으니 이분 탐색 또는 파라메트릭 서치를 이용해 풀 수 있습니다.

 

또 이 문제는 가능한 정답들 중에서도 제일 큰 값을 찾아야하는 문제이므로, 가능한 탐색 범위를 모두 확인해야합니다. 따라서 이 문제는 이분 탐색이 아닌 파라메트릭 서치로 푸는 문제입니다.