[백준] 1654 - 랜선 자르기

1. 문제

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

1654번: 랜선 자르기

 

2. 접근

1. 이코테를 풀어봤다면 ' 떡볶이 떡 만들기 ' 문제랑 유사하다 => 파라메트릭 서치!

2. n의 범위가 커서 이분탐색을 사용하면 된다

3. k개를 분할해서 n개의 '동일한 길이'의 랜선을 만들어야 하므로 start, end 를 길이에 대한 끝 점들의 값으로 설정해준다

4. 랜선들의 값들을 mid 값으로 나눠서 tot 값에 합산해 간다

5. 분할된 랜선들의 총 개수가 n에 비해서 작은지 크거나 같은지에 따라 res에 mid 값을 넣어서 확인하면 된다

 

3. 풀이

import sys
input = sys.stdin.readline

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

line = []
for i in range(k):
    line.append(int(input()))

line.sort()

start = 1
end = max(line)
res = 0

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

    for l in line:
        tot += l // mid
    
    if tot < n:
        end = mid - 1
    else:
        start = mid + 1
        res = mid

print(res)