[Python] 1654 - 랜선 자르기

1. 문제 정의

이미 가지고 있는 랜선의 갯수와 필요한 랜선의 갯수가 주어진다. 이미 가지고 있는 랜선들의 길이가 차례대로 주어지고, 이들을 잘라 필요한 만큼의 랜선을 구하도록 할 때, 그때의 랜선들의 최대 길이를 구하는 문제이다.

 

2. 풀이 방식

이분 탐색을 활용하여 문제를 해결하였다.

 

먼저 입력받은 랜선의 길이를 리스트로 저장한 다음, 리스트 내부에서 이분탐색을 진행하기 위해 start 값을 1, end 값을 길이의 최댓값으로 설정하였다. 

 

기존의 랜선의 길이와 mid 값을 나눈 몫이 자른 후의 랜선의 개수가 되고, 이를 새로운 리스트 num_rope에 저장하였다.

이후 sum(num_rope)의 값이 N보다 작을 경우, end값을 조정하여 더욱 잘개 자르도록 하였고, N보다 클 경우 start값을 조정하여 while문의 종료 조건을 만족하도록 하였다.

 

while문이 종료된 후의 end값이 최대 길이가 된다.

# 1654 랜선 자르기

K, N = map(int, input().split())

rope = [] # 랜선의 길이 저장
for _ in range(K):
    length = int(input())
    rope.append(length)

start, end = 1, max(rope)

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

    num_rope = [] # 자른 후의 랜선의 개수 저장
    for i in rope:
        num_rope.append(i // mid)
        
    if (sum(num_rope) < N): # 랜선의 개수가 필요 랜선의 개수보다 작을 경우
        end = mid - 1 # mid값을 조정하여 더 잘개 자르도록 조정
    elif (sum(num_rope) >= N): # 랜선의 개수가 필요 랜선의 개수보다 클 경우
        start = mid + 1 # mid값을 조정하여 덜 잘개 자르도록 조정

print(end) # start값이 end값보다 커질 때, while문이 종료되고 이때의 end값이 최대 길이가 된다.

 

3. 후기

랜선의 길이에 대해 중앙값을 설정한 후 반복문을 통해 조정해 나가 최대 길이를 찾는 비교적 단순한 문제였다고 생각이 든다.

 

문제에 조건 중, N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 라는 조건을 간과하고 문제를 풀어 첫 시도때에는 실패하였다. 이후 문제를 다시 한 번 읽어본 후 해당 조건을 만족하도록 코드를 다시 작성하였고, 결과적으로 문제를 해결하게 되었다.