[백준] 1656 - 랜선 자르기 (Python)

문제 출처:

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

문제 풀이:

• 나무 자르기 문제와 매우 흡사한 문제이다. 이진탐색으로 풀면 가능하다
• 이 문제에서는 target이 잘라야 하는 랜선 길이라고 두고 매번 갯수를 파악하면서 n개를 기준으로 right,left를 조정하면된다.

k,n = map(int,input().split())

lans = []
for _ in range(k):
    lans.append(int(input()))


left = 1
right = max(lans)
max_val = 0
while(left<=right):
    mid = (left+right)//2
    len_lans = 0
    for i in lans:
        len_lans += i//mid

    if(len_lans>=n):
        left = mid+1
        if(mid >max_val):
            max_val = mid
    else:
        right = mid-1

print(max_val)