백준 2805번 나무 자르기 [파이썬]

www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

이 문제는 원하는 나무길이만큼만 베기 위한 베어내는 최대 높이를 설정하는 문제로, 이진탐색법을 이용하면 풀 수 있다.  

내 접근법도 이진탐색법이지만, 베어내는 나무길이와 높이가 있는 2차원 리스트를 만들기까지 하는 아주 복잡한 식으로 구현했다. 그래서 아래와 같이 내 코드는 길고 복잡하다.

N, M = map(int, input().split()) # N = total number of trees, M = Target total lenght of trees
trees_length = list(map(int, input().split()))
max_tree = max(trees_length)

cut_heigth = []
for i in range(1, max_tree):
    cut_heigth.append(i)

total_cut_lengths = []
for j in cut_heigth:
    cut_tot_len = 0
    for k in trees_length:
        # total_cut_length = 0
        j_cut = [j]
        if k >= j:
            cut_tot_len += (k - j)
            # print(total_cut_length)   
        else:
            cut_tot_len += 0
    j_cut.append(cut_tot_len)
        # print(cut_len)		
    total_cut_lengths.append(j_cut)

# print(lengths)
print(total_cut_lengths)

def is_target_length(target, array):
    current_min = 0
    current_max = len(array) - 1
    current_guess = (current_min + current_max) // 2

    while current_min <= current_max:
        if M == array[current_guess][1]:
            return array[current_guess][0]
        elif M < array[current_guess][1]:
            current_min = current_guess + 1
        else:
            current_max = current_guess - 1
        current_guess = (current_min + current_max)//2
    
    return array[current_guess][0]

print(is_target_length(M, total_cut_lengths))

 

원하는 답이 나오지만 이 코드를 짠 나도 시간이 지나면 설명이 어려울 정도로 복잡하고 길다.

하지만 구글링해서 찾은 풀이는 허무할 정도로 짧았는데, 핵심만 담은 참신한 아이디어라서 더 놀랐다.

# 이진탐색으로 해결
N, M = map(int, input().split()) # N = total number of trees, M = Target total lenght of trees
trees_length = list(map(int, input().split()))
max_tree = max(trees_length)

start = 1
end = max_tree

# 이진탐색을 자르는 높이를 바꿔 가는 것으로 구현했다.
# 그래서 자르는 높이의 첫 값은 가장 높은 나무의 중간 높이다.
while start <= end:
    mid = (start + end) // 2
    log = 0
    
    for i in trees_length:
        if i >= mid:
            log += i - mid
    
    if log >= M:
        start = mid + 1
    else:
        end = mid - 1

print(end)

나는 자르는 높이에 따른 베어내는 총 길이를 다 구하는 과정을 거친 다음 이진탐색을 쓰는 접근법이라 코드가 길고 복잡해졌다면, 이 코드는 처음부터 '자르는 높이'를 가장 높은 나무의 중간값으로 설정해서  잘린 나무들의 총길이를 바로 구해서 탐색하는 방식이다. 다시 말해, 내가 둘로 나눈 과정을 한큐에 몰아치기 했다는 뜻이다. 어차피 자르는 높이를 구하면 된다는 문제의 본질을 간파하니  이렇게 쉬운 코드를 짤 수 있는 것이다.

나도 이런 식으로 디테일을 무시하고 문제의 핵심을 재빨리 간파하는 '무시'라는 수학적 사고법을 기르는 것이 목표다.