[Baekjoon, Python] 2805번: 나무 자르기

도입

백준 단계별 풀기에서 이분탐색 네 번째 문제이다.

백준 2805번 문제, 입력, 출력

---

백준 2805번 입출력 예제 1

---

풀이

 1. 이전의 랜선 자르기와 구조는 같고, 계산 로직만 다르다. 랜선 자르기의 경우 랜선의 각 길이들을 mid값으로 나눈 몫을 개수로 count하여 Target에 도달하는 지를 본다면, 나무 자르기의 경우 나무의 각 길이들에서 mid값을 뺀 나머지의 합이 Target에 도달하는 지를 확인한다.

 

 2. '시간초과(TLE)'로 고생할 수 있다. def binaryTree로 나무 길이 합을 구하는 함수를 정의하여 TLE를 해결 하였다. Pypy3 구현체로 해결하는 방법도 있다.

 

---

코드

다음 코드는 python3 로 해결한 문제이다. 

from sys import stdin

def binaryTree(T,list_K):
    high_h, low_h = max(list_K), 0       # Key point 

    while low_h <= high_h :                 # 로우 <= 하이
        mid_h = (high_h + low_h)//2         # 중간 값
        count = 0							# 자른 나무의 합
        for x in list_K:					# *Main 로직*
            if x > mid_h:
              count += x-mid_h
        if count  < T:                         # T을 못채운 경우
            high_h = mid_h - 1
        elif count >= T:                      # T을 채우거나 넘긴경우 (달성)
            low_h = mid_h + 1
            rtn = mid_h

    return rtn

K, T = map(int,stdin.readline().split())
list_K = list(map(int,stdin.readline().split()))

print(binaryTree(T,list_K))

python3

시간이 3036ms나 나왔다. 만약에 def로 binaryTree 함수를 정의하지 않고 그냥 푼다면, 시간초과가 날 것이다.

from sys import stdin

K, T = map(int,stdin.readline().split())
list_K = list(map(int,stdin.readline().split()))

high_h, low_h = max(list_K), 0       # Key point 

while low_h <= high_h :                 # 로우 <= 하이
    mid_h = (high_h + low_h)//2         # 중간 값
    count = 0
    for x in list_K:					# *Main 로직*
        count += x-mid_h if x-mid_h>0 else 0
    if count  < T:                         # N을 못채운 경우
        high_h = mid_h - 1
    elif count >= T:                      # N을 채우거나 넘긴경우 (합격)
        low_h = mid_h + 1
        rtn = mid_h

print(rtn)

Pypy3

위의 코드는 pypy3로 해야 통과할 수 있다. 시간은 528ms로 빨라졌다. 해당 코드를 python3로 돌리면 '시간초과(TLE)'를 볼 수 있다.

---

마무리

이분탐색이 무엇인지만 알고 있다면, 쉽게 해결할 수 있는 문제이다. 시간초과로 애를 먹긴 했지만.....