1654 랜선 자르기

알고리즘 공부

문제 보기

아이디어

이분 탐색 으로 랜선을 자를 길이를 정한다.

오답

import sys
input = sys.stdin.readline

k, n = map(int, input().strip().split())
lan = [int(input().strip()) for _ in range(k)]

start, end = 1, max(lan)
while start <= end:
    # 만들 랜선의 길이
    x = (start+end)//2
    # 랜선 개수 
    numOfLan = 0
    for l in lan:
        numOfLan += l//x
    # 너무 많음
    if numOfLan > n:
        start = x+1
    # 적음
    elif numOfLan < n:
        end = x-1
    # 딱 맞음
    else:
        break
print(x)

원인

numOfLan = n인 경우 그 때의 x값을 바로 출력하는 것이 원인이였다.
102cm 랜선을 2개로 자른다면 50cm로 잘라도 2개, 51cm로 잘라도 2개이기 때문이다.
n개를 만들 수 있는 길이 x를 찾더라도 x보다 더 긴 길이에 대해서도 계산해봐야 한다.

정답

import sys
input = sys.stdin.readline

k, n = map(int, input().strip().split())
lan = [int(input().strip()) for _ in range(k)]

start, end = 1, max(lan)
while start <= end:
    # 만들 랜선의 길이
    x = (start+end)//2
    # 랜선 개수
    numOfLan = 0
    for l in lan:
        numOfLan += l//x
    if numOfLan >= n:
        start = x+1
    elif numOfLan < n:
        end = x-1

print(end)