[Algorithms] 결정&그리디 알고리즘-랜선 자르기(결정 알고리즘)

 

import sys
 
sys.stdin = open("input", "rt")
n, m = map(int, input().split())
rope = [int(input()) for _ in range(n)]
 
first = 1
last = max(rope)    # 찾고자 하는 길이는 가장 큰 로프의 길이 보다 짧다
res = 0
 
while(first <= last):
    mid = (first+last)//2   # first 와 last 사이의 mid 길이를 구해서
    cnt=0                   
    for i in range(n):
        cnt += rope[i]//mid # mid라는 일정한 길이로 자른 로프들이 몇개가 나오는지 카운트해서 더한다
 
    if cnt >= m:            # 정해진 개수보다 크거나 같다고 해도 된다고 하였으니
        res = mid           # 일단 m 이상인 값이 나오면 결과값이라고 저장을 하고
        first = mid+1       # 더 긴 길이를 찾아나선다
    else:
        last = mid-1        # m의 수에 못 미치면 길이가 너무 길다는 얘기이므로 last포인터를 mid-1만큼 줄여준다
 
print(res)