[문제풀이] 나무 자르기

나무 자르기

짬짬이 이틀을 소비했는데 정답을 맞추지 못했다.

풀이 시간: ??시간

접근방법

첫 시도:

처음에는 최소나무와 최대나무를 나무들의 평균을 구해서 재귀함수로 분할 정복을 하려 했다.

import sys

def tree_cut(trees,n):
    filter_tree = [0]
    for tree in trees:
        if tree-n > 0:
            filter_tree.append(tree-n)
    
    #print(filter_tree)
    
    return sum(filter_tree)
    

def search_height(mid,trees,ref):
    
    tot2 = tree_cut(trees,mid)

    if tot2 == ref:
        print(f'{mid}')

    if ref > tot2:
        search_height(mid-1,trees,ref)
    elif ref < tot2:
        search_height(mid+1,trees,ref)

num,value = map(int,sys.stdin.readline().split())

trees= list(map(int,sys.stdin.readline().split()))

mid = max(trees)+min(trees)//2
search_height(mid,trees,value)
#print(trees)

시간초과....

2~n 시도:

재귀함수로는 시간 초과가 뜬다는 제보를 받고 반복문으로 재도전. .

n, m = map(int, input().split())
tree = list(map(int, input().split()))


def cut_tree(trees,cut):
    tot =0
    for t in trees:
        if 0 < t-cut:
            tot += t-cut
    return tot
    
# 이진 탐색을 위한 시작점, 끝점
src = 0
dst = max(tree)

result = 0 # 최종 절단기 높이
mid = (src+dst)//2
#print(mid)
while result != m:
    mid = (src+dst)//2
    result = cut_tree(tree,mid)
    #print(result)
    if result > m:
        src = mid
    elif result <= m:
        dst = mid-1

print(mid)

다시봐도 필요한 부분만 딱 깔끔하게 쓴 것 같다. 하지만 시간 초과...

결국 내 한계를 느끼고 GPT에게 help 요청 했다.

개선 코드

n, m = map(int, input().split())
tree = list(map(int, input().split()))

def cut_tree(trees, cut):
    return sum((t - cut) for t in trees if t > cut)

# 이진 탐색 범위
low = 0
high = max(tree)
answer = 0

while low <= high:
    mid = (low + high) // 2
    total = cut_tree(tree, mid)

    if total >= m:
        answer = mid  # 조건 만족 → 높이 더 높여볼 수 있음
        low = mid + 1
    else:
        high = mid - 1

코드 비교

문제	해결 방법
while result != m: 조건	while low <= high:로 수정
src = mid	src = mid + 1 (같은 mid 반복 방지)
cut_tree 내 조건	if t > cut으로 간결하게
중간 결과 출력	print(result) 제거 (제출 시 시간 초과 유발 가능)

두개를 놓고 비교해보면 약간 씩 다름을 느낀다.
특히 내가 간과했던 반례부분을 짚어주었고, while 조건과 반복문안에 if문에 약간의 차이가 있다. 확실이 생각을 못한 부분까지 짚고 있다.

내가 짠 코드를 보면

while result != m:

이것은 무조건 m과 딱 맞아 떨어져야 반복문이 종료되는 조건이다.
하지만 이 문제는 적어도 딱 맞아떨어지는 이라는 문구가 있어 근사치까지는 수용이 가능한 문제 같다.

    if result > m:
        src = mid
    elif result <= m:
        dst = mid-1

그 외에는 디테일 부분에 차이가 있는데... 좀 더 분할 정복에 대해 학습 후 개념을 다시 정리 할 필요가 있을 것 같다.

그리고, 코드를 짜다가 하나하나 바꾸다보면 점점 미궁으로 빠져드는 느낌이다
항상 목표성을 가지고 수정하기전에 수정하는게 목적에 부합한지 생각하고 코드 개선 및 수정하는 습관을 들이도록 하자