[코딩테스트 공부] 랜선 자르기

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

문제 분석

문제의 조건을 보게 되면, 시간 제한은 2초이고, K는 10000 이하로 제한이 되어있습니다. 따라서 O(N^2)까지의 복잡도가 허용된 상황이지만, 이 문제는 이분탐색으로 풀 수 밖에 없습니다. 이유는 다음과 같습니다.

• 데이터의 리스트만으로 특정한 정수 값을 도출해야합니다.
• 특정한 정수 값이 데이터 리스트 안에 존재하는 값이라는 보장이 존재하지 않기 때문에, 다른 방식으로 값을 도출해야합니다.
• 위의 제약 조건들을 분석해보면, 이분탐색이 최적이라는 것을 단박에 알아차릴 수 있습니다.

이 문제는 이전의 나무 자르기 문제와 풀이 방법이 매우 유사합니다. 코드를 확인하겠습니다.

코드를 확인해볼까요?

import sys

input = sys.stdin.readline

K, N = map(int, input().split())
line_length_list = []

for _ in range(K):
    line_length_list.append(int(input()))
    
start, end = 1, max(line_length_list)

# 이분 탐색 시작
while start <= end:
    sum = 0
    mid = (start + end) // 2
    
    for length in line_length_list:
        sum += length // mid
        
    if sum >= N:
        start = mid + 1
    else:
        end = mid - 1
        
print(end)

이전의 나무 자르기 문제와 풀이 방법이 똑같기 때문에, 간단하게만 설명드리겠습니다.

start는 1, end의 경우 랜선의 최대 길이로 잡고, 이분 탐색을 시작합니다.
랜선의 경우, mid의 값으로 나눈 나머지만큼 챙길 수 있기 때문에 length에 mid를 나눈 몫 만큼을 sum에 반영합니다.

sum의 값에 따라서, start 혹은 end의 값을 조절해주면 됩니다.

• sum이 N 이상일 경우 : 조금 더 길게 잘라도 되니까 start의 값을 조절
• sum이 N 미만일 경우 : 조금 더 짧게 잘라야하기 때문에 end의 값을 조절

따라서, 마지막에는 end를 출력하면 문제는 해결됩니다.