백준 1654: 랜선자르기 (Python) - 이진탐색 알고리즘

문제

1654번: 랜선 자르기

 

이진탐색의 가장 기본적인 문제이다. 하지만 나는 다 까먹어서 다시 공부했다...

가지고있는 k개의 랜선을 잘라 같은 길이로 n개를 만들 수 있는 최대 길이를 출력하는 문제이다.

 

 

풀이

k, n = map(int, input().split())
lan = []

for i in range(k):
    lan.append(int(input()))

lan.sort()  # 이분탐색을 위해 정렬
s = 1
e = max(lan)

res = 0
while s <= e:
    total = 0
    mid = (s + e) // 2

    for x in lan:
        if x >= mid: total += (x // mid)

    if total < n:
        e = mid - 1
    else:
        res = mid
        s = mid + 1

print(res)

 

 

현타...ㅎㅎ 알고리즘도 종종 풀어줘야 잊지 않는거 같다...

공부할게 넘 많아~~~~