[정렬/탐색] 백준 1654 랜선 자르기 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1654번: 랜선 자르기

 

 

 

2. 문제 풀이

 K개의 랜선을 잘라서, 동일한 길이의 N개 랜선을 만드는 문제입니다. 이 때, N개 랜선의 최대 길이를 구해야 합니다.

 

2022.02.09 - [Algorithm] - [Algorithm] 이진탐색(Binary Search), 반반 나누어서 찾자

[Algorithm] 이진탐색(Binary Search), 반반 나누어서 찾자

 가장 쉬운 방법은 랜선의 길이를 1씩 늘리면서, N개의 랜선이 만들어지는지 확인하는 방법입니다. 하지만 이는 시간초과를 피할 수 없습니다...

 그 대신, 이진 탐색을 이용합니다. 가장 짧은 랜선 길이인 '1'과 가장 긴 랜선 길이인 'max(k개의 랜선)' 사이에서 이진 탐색으로 N의 최대길이를 찾습니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

K, N = map(int, input().split())
lanCable = []
for i in range(K):
    lanCable.append(int(input()))

start, end = 1, max(lanCable) # 랜선 길이의 최소, 최댓값
# 랜선길이를 찾는 이진 탐색
while start <= end:
    mid = (start+end)//2
    lan = 0 #랜선 수
    for i in lanCable:
        lan += i // mid # 중간 길이로 분할된 랜선 수

    # N보다 랜선 갯수가 많을 경우, 더 길게 자르기
    if lan >= N:
        start = mid + 1
    else: # 랜선 갯수가 적으며, 더 짧게 자르기
        end = mid - 1
print(end)

 이진탐색에 쓰이는 정렬된 자료는 1부터 max(lanCable)까지 1씩 오름차순된 리스트입니다. N보다 랜선 갯수가 많은 경우, 더 길게 잘라야 합니다. 따라서 위쪽 영역 (mid+1 ~ end)을 탐색합니다.

 반대로, N보다 랜선 갯수가 적은 경우에는 더 짧게 잘라야 합니다. 이 때는 아랫 영역 (start ~ end-1)을 탐색합니다.