[이분탐색] 백준 1654. 랜선 자르기

문제 바로가기

 

문제 해석

1. n개의 랜선 만들어야 함
2. 이미 k개 있음
3. 같은 길이로 만들자
4. 최대 길이는?
   : 가지고 있는 랜선을 같은 길이로 잘라서 n개로 만들 것이다. n개는 고정인데, 길이를 가장 길게 한다면 그 값은 무엇일까?

주요 변수

다른 이분탐색처럼 low와 high로 탐색의 범위를 정한다. 문제의 조건에서 k<=n 이라고 했기 때문에, 가장 긴 놈보다 길게 자르게 되면 k개보다 적게 n개가 나오게 때문에 answer는 가장 길게 잘랐을 때의 범위를 벗어 날 수 없다. 따라서 high = max(랜선리스트)이다.

 

다만, n개의 랜선이 n번의 input으로 입력되어 list를 만든다. n의 범위가 1,000,000 까지 있을 수 있기 때문에, max함수를 쓰면 효율성이 시간 복잡도가 늘어나기 때문에 입력을 받으면서 두개씩 비교하는 방식을 택했다.

코드

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

# lan = [int(input()) for _ in range(k)]
long = -1
lan = []
for _ in range(k):
    i = int(input())
    long=max(long,i)
    lan.append(i)

def getCnt(mid):
    tot = 0
    cnt = 0
    for i in range(k):
        cnt = lan[i]//mid
        tot += cnt
    return tot

low = 1
high = long
ans = 0
while low <= high:
    mid = (low + high)//2
    if getCnt(mid) >= n:
        ans = mid
        low = mid +1
    else:
        high = mid-1
print(ans)