백준 : 2805 나무 자르기

나무 자르기 문제는 이진탐색을 활용하여 나무를 자를 수 있는 최대 길이를 찾는 문제이다.

변수 설정

N : 나무의 수 , M : 가져갈 나무 길이의 총합

h : 자를 나무의 길이

height : 자르는 지점 (target)

나무의 길이가 h보다 클때, h - height 의 값의 합이 7 (M) 이 될때 height의 최대값을 구해야 한다.

최종 코드는 다음과 같다.

import sys
def find_height(left, right, target):
    best = 0
    while left <= right :
        mid = (left + right) // 2
        total = 0
        for tree in h :
            if tree > mid :
                total += tree - mid
        if total >= target :
            best = mid
            left = mid + 1 
        else : 
            right = mid - 1
    return best

N, M = map(int, sys.stdin.readline().split())
h = list(map(int, sys.stdin.readline().split()))
left = 0
right = max(h)
result = find_height(left, right, M)
print(result)

시행착오 1 . While 문을 재귀함수 밖에 설정

입력값을 받는 부분 밑에 while 문으로 왼쪽과 오른쪽 값을 하나씩 움직이는 코드를 밖에 두었더니, 시간 초과로 문제를 풀지 못했다. 반례를 보니, 숫자가 커질때 재귀함수 밖에 선언된 부분을 불러오는 과정에서 데이터를 처리할 수 없었다.

while left <= right :
    mid = (left + right) // 2
    result = find_height(mid, M, 0)
    if result :
        answer = result
        right = mid -1
    else :
        left = mid +1
print(answer)

시행착오 2. Total을 구하는 값에서 리스트 순회

재귀함수에서 자른 나무의 합을 구할때 리스트를 다시 순회하는 과정에서도 시간 초과로 문제를 풀지 못했다. 동일하게 리스트가 길어질때 값을 다시 순회하는 과정이 비효율적이다.

total = sum(tree - mid for tree in h if tree > mid)

시행착오 3. if 문에서 재귀함수 호출

입력값이 커지면 재귀함수를 다시 호출하며 mid 값을 바꾸는 부분에서 RecursionError 발생할 수 있다.

조건을 만족하는 mid를 따로 저장하는 값이 없어, total이 target 이상이어도 그 값을 기억하지 않고 계속 이동한다. 조건을 만족하는 mid 값 중 가장 큰 값을 기억하지 않으면 최적값을 찾을 수 없다.

또한 문제는 최적의 길이를 찾는 것이지, 항상 target과 일치하는 값을 찾는게 아니기에 mid 값이 리스트에 없는 경우 target과 일치하지 않아 오답을 반환한다.

if total == target :
	print(mid)
	return mid
total = 0
if total >= target :
	return find_height(left, mid-1, target)
else : 
	return find_height(mid+1, right, target)

확인 필요 1. right = h[N-1]

처음에 right 값을 h 리스트의 마지막 값으로 설정했으나, GPT에 따르면 max 함수를 쓰는것을 권장한다. 그 이유는 리스트가 커졌을때, 만약 그 리스트가 정렬되지 않았다면 h(N-1)은 항상 리스트의 최대값이 아닐 수 있다. max 함수로 연산을 하는것 보다는 h(N-1)로 리스트의 마지막 값을 받아오는 것이 더 빠르지만, 결국 리스트 내의 최대값이 아닐 경우 재귀 함수의 깊이가 증가할 수 있으니 max 값을 받아와서 넘겨주는 것을 추천한다.

확인 필요 2. sys로 입력값 받는법 통일화

GPT에 따르면 sys로 입력을 받는 부분이 있다면 일반 값을 받을때 input으로 따로 받는것 보다 sys로 통일하는 것이 최적화에 좋다고 한다. 이게 진실인지는 모르겠다. 메모리나 시간이 넉넉한 문제에서는 크게 문제되지 않았다.