백준 1654 풀이 (랜선 자르기, parametric search, 파라매트릭 서치)

파라매트릭 서치는 이분탐색을 활용하여 최대 혹은 최소를 구하는 방법이다.

예를 들어 1~10까지중 5를 확인해보고 최소를 구해야된다면 5부터 10까지 버린다.

그럼 1~4안에서 비교를 하며된다. 이러한 방식으로 절반값을 확인하며 최대 혹은 최소를 구하는 방법이다.

 

딱히 설명할게 없어서 바로 이론을 학습하고 바로 코딩에 들어갔다.

import sys
k,n = map(int, sys.stdin.readline().split())
small = 2**32-1
lan = []
for _ in range(k):
    t = int(sys.stdin.readline())
    lan.append(t)
    if t < small:
        small = t
l = 1
r = max(lan)
mid = small
while l != r:
    count = 0    # count
    for i in lan:
        count += i//mid
    if count >= n: # 성립하는 경우
        l = mid
    else: # 성립하지 않는경우
        r = mid-1
    mid = (l+r+1) // 2
print(mid)

나는 조금 의외였던게 r = max(lan)일때는 무리가 없이 통과를 했지만, r을 small로 두면 통과가 되지 않았다.

내가 생각할때 연산을 줄이기 위해서는 오른쪽 인덱스가 최소값이 들어와야한다고 생각했다. 그러나 안된다;; 왜그런지는 모르겠다.