[Python] 2905 - 나무 자르기

1. 문제 정의

나무의 개수와 원하는 나무의 길이가 주어지고, 나무들의 길이가 주어진다. 이 나무들을 적절히 잘라 원하는 길이 만큼을 가져가기 위해 절단기에 설정할 수 있는 최대 높이를 구하는 문제이다.

이해를 돕기 위한 그림

파란 부분이 원하는 길이 M이고, 우리가 구해야 할 출력은 x이다.

 

2. 풀이 방식

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

 

입력으로 받은 나무의 길이를 저장하는 리스트를 생성한다. 

이후 이분 탐색을 위한 start 값, end 값을 각각 1, 최대 높이로 설정한다.

 

while문을 통해 start 값이 end 값보다 커지면 while문을 벗어나도록 설정한 후, 

지정한 중앙값에 대해 얻을 수 있는 나무의 길이를 저장한다. 이후 원하는 길이(M)보다 클 경우 시작 지점(start)을 조절하여 중앙값을 조절한다.

원하는 길이보다 작을 경우, 끝 지점(end)를 조절하여 중앙값을 조절하도록 한다.

# 2905 나무 자르기

N, M = map(int, input().split())
tree = list(map(int, input().split()))
start, end = 1, max(tree)

# 이분 탐색
while (start <= end):
    mid = (start + end) // 2

    # 현재 얻은 나무의 길이
    wood = 0
    for i in tree:
        if (i > mid): # 나무의 길이가 중앙값보다 크다면
            wood += (i - mid) # 나무를 잘라 냄

    if (wood >= M): # 처음 설정한 중앙값 기준으로 얻은 나무의 길이가 원하는 길이보다 길다면면
        start = mid + 1 # 시작점을 조절하여 중앙값을 다시 조절하도록 함
    else: # 아닐경우
        end = mid - 1 # 끝점을 조절하여 중앙값을 다시 조절하도록 함

print(end) # while문 종료 후 end 값이 최대 나무의 길이가 된다.

 

3. 후기

처음에 그림을 저렇게 그려서 그런가, max값으로 부터 1씩 감소하며 답을 찾는 방식으로 문제를 풀었다. 그런식으로 하니 리스트 내 반복을 각 case마다 돌아서 그런지 당연하게도 시간초과가 떳다... 이후 이분 탐색에 대한 정의를 다시 한 번 되짚어 보았다.

아마 코테 준비를 하며 처음 풀어본 이분 탐색 문제인것 같은데, 이번을 계기로 앞으로의 이분 탐색 문제는 잘 해결할 수 있도록 준비를 해야겠다.