[알고리즘] 백준 1654 - 랜선 자르기

문제

랜선 자르기

접근

1. 이코테의 떡볶이 떡 자르기와 비슷하다

2. 다만 다른점은 떡볶이 떡 자르기는 자르고 났을때의 남은 떡의 양을 비교하는 반면에 이 문제는 n개의 랜선으로 나와야 한다는 점이다.

3. 방식은 같은데 배열에 있는 모든 랜선들을 mid 값으로 나눠서 total에 저장을 하고 그 값을 n의 개수와 비교해서 start, end의 위치를 옮긴다.

 

풀이

# 랜선 자르기 - 떡볶이 떡 자르기랑 비슷
import sys
input = sys.stdin.readline

k, n = map(int, input().split())
array = []
for i in range(k):
    array.append(int(input()))


start = 1
end = max(array)

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

    for x in array:
        total += x // mid  # 전부 mid로 나눠서 나오는 갯수를 체크
    if total >= n:  # n은 나눠져야할 총 랜선의 개수
        start = mid + 1
    else:
        end = mid - 1

print(end)