[백준] 1654번 랜선 자르기(파이썬))

문제

1654번: 랜선 자르기

코드

import sys
input = sys.stdin.readline

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

# long이 최대 길이는 max(li)
short, long = 1, max(li)

# short가 long보다 길어지면 멈춰
while short <= long:
    # 둘은 더한 값 % 2를 해준다
    cut = (long + short) // 2
    lines = 0
    # li에 있는 것을 다 비교해 중간 값으로 잘랐을때 라인의 수를 구해준다
    for i in li:
        lines += i // cut
    
    # 라인의 지정 개수보다 많다면 short를 줄여서 더 긴 길이가 나와 랜선이 더 적은 개수가 나오도록 범위를 줄인다
    if lines >= n:
        short = cut + 1
    # 개수보다 적다면 long을 줄어서 더 짧은 길이가 나와 랜선이 더 많이 나오게 범위를 줄인다.
    else:
        long = cut - 1
print(long)

해설

이진 탐색으로 범위를 줄여나가면서 푸는 문제였다. 랜선이 여러개 존재해서 그걸 다 어떻게 가져와서 랜선 개수를 구할지가 고민이었다. 

for로 다비교해서 라인을 하나하나 구해서 범위를 줄여가났다. 한번 틀려서 찾아보니 +1, -1을 안해주면 길이가 제대로 나오지 않아서 생긴문제였다.