[백준 1654 랜선 자르기][파이썬] Parametric Search (이분 탐색) 접근 방법

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

1654번: 랜선 자르기

백준 1654번 문제는 이분 탐색을 이용하는 Parametric Search의 기본적인 문제이다.

 

Parametric Search를 사용하기 위해서는 문제를 결정 문제로 바꿀 수 있어야 한다.

 

위 문제의 경우 자를 랜선의 길이를 임의로 x라고 했을 때 랜선 N개를 만들 수 있다면 True를, 없다면 False를 반환하는 문제로 바뀌게 된다.

 

그러면 이제 x의 최대 길이를 구하기 위해 이분 탐색을 사용할 수 있다.

 

위 문제에서 예제 입력 1번을 예시로 든다면 우선 low를 1로, high를 가장 긴 랜선의 길이인 802로 정한다.

 

그리고 이 중간 값인 mid는 401이 될 것이고 mid 길이 만큼 자를 때 랜선 N개를 만들 수 있다면 mid보다 더 크게 잘라도 되는지를 확인해야 하기 때문에 low에 mid+1 값을 넣어서 반한다.

 

만약 만들 수 없다면 그 보다 더 짧게 잘라야 하므로 high에 mid-1 값을 넣어서 반복한다.

 

그러다 high가 low보다 작아지는 순간에 반복을 멈춘다.

 

시간 복잡도를 계산해보면 우선 랜선 N개를 만들 수 있는지 판단할 때의 시간 복잡도는 O(N)이다.

 

현재 가지고 있는 모든 랜선에 대해서 각각 mid로 나눈 값(소숫점 버림)을 모두 더해서 N과 비교하면 되기 때문이다.

 

그리고 가장 최대 길이를 찾기 위한 과정은 이분 탐색으로 진행되기 때문에 시간 복잡도는 O(log N)이다.

 

즉 전체 시간 복잡도는 O( N log( N ) )이 된다.

 

import sys
input=sys.stdin.readline
k, n = map(int, input().split())
li=[0]*k
for i in range(k):
    li[i]=int(input())
standard = max(li)
res=0
def binary(low, high):
    if high<low:
        return
    global n
    global res
    mid=(low+high)//2
    temp=0
    for i in li:
        temp+=i//mid
    if temp>=n:
        res=mid   
        binary(mid+1, high)
    else:
        binary(low, mid-1)
binary(0, standard*2)
print(res)