[BOJ] 1654 / 랜선 자르기 / Python 파이썬

[BOJ] 1654 / 랜선 자르기 / Python 파이썬

[BOJ] 1654 / 랜선 자르기 / Python 파이썬

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

1654번: 랜선 자르기

 

풀이

이분 탐색의 기본 문제이다.

 

첫 시도는 완전 탐색으로 접근하였지만 당연히 시간초과가 발생 하였다.

가장 기본적인 이분 탐색의 구조로 해결 하였다.

 

import sys
input = sys.stdin.readline


K, N = map(int, input().split())

lines = []

for _ in range(K):
    lines.append(int(input()))

end = max(lines)
start = 1

while start <= end:
    mid = (start+end) // 2
    res = 0

    for l in lines:
        res += l // mid

    if res < N:
        end = mid - 1
    else:
        start = mid + 1

print(end)