[baekjoon] 백준 2805번(파이썬): 나무 자르기

문제

2805번: 나무 자르기

알고리즘

- 이분 탐색을 통해 문제를 수행한다.

- 반복문을 통해 절단기로 나무를 자른 후 가져갈 수 있는 나무의 높이를 구한다.

- 가져갈 수 있는 나무의 높이가 가져가려 하는 나무의 높이보다 크면 더 이상 가져갈 수 있는 나무의 높이를 구하지 않아도 되므로 반복을 멈춰준다.

- 가져갈 수 있는 나무의 높이가 가져가야 하는 나무의 높이보다 크거나 같으면 절단기의 높이를 올려준다.

- 반대로 가져가야 하는 나무의 높이가 작으면 절단기의 높이를 내려준다.

- 절단기의 최댓값이 최솟값보다 작아지고 난 후에 절단기의 최댓값을 출력한다.

- 절단기의 최댓값이 적어도 가져가야 하는 나무의 높이를 자를 수 있는 절단기의 높이이다.

코드

import sys
n, m = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))
_max = max(tree) # 가져갈 수 있는 나무의 높이의 최댓값
_min = 1 # 가져갈 수 있는 나무의 높이의 최솟값

# 이분탐색
# 최댓값이 최솟값보다 작아질때까지 반복
while _max >= _min:
    mid = (_max + _min) // 2 # 절단기의 높이
    res = 0 # 가져갈 수 있는 나무의 높이의 합

    # 반복문을 통해 절단기로 나무를 자른 후
    # 가져갈 수 있는 나무의 높이를 더한다.
    for i in tree:
        if i > mid:
            res += i - mid

            # 가져갈 수 있는 나무의 높이가
            # 가져가려하는 나무의 높이보다 크면 반복을 멈춘다.
            if res > m:
                break

    # 가져갈 수 있는 나무의 높이가 가져가야 하는 높이보다 크거나 같으면 절단기의 높이를 올려주기 위해
    # 가져갈 수 있는 나무의 높이의 최솟값을 절단기의 높이에 + 1 해준 값으로 초기화한다.
    if res >= m:
        _min = mid + 1

    # 가져갈 수 있는 나무의 높이가 가져가야 하는 높이보다 작으면 절단기의 높이를 내려주기 위해
    # 가져갈 수 있는 나무의 높이의 최댓댓값을 절단기의 높이에 - 1 해준 값으로 초기화한다.
    else:
        _max = mid - 1

# 절단기의 최댓값 출력
print(_max)

 

실패한 코드(시간 초과)

import sys
n, m = map(int, sys.stdin.readline().split())

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

_max = max(tree)
_min = 1

while _max >= _min:
    mid = (_max + _min) // 2
    res = 0

    for i in tree:
        if i > mid:
            res += i - mid

    if res >= m:
        _min = mid + 1

    else:
        _max = mid - 1

print(_max)

시간 초과를 줄이기 위해, 가져갈 수 있는 나무의 높이를 구하는 과정에서 가져갈 수 있는 나무의 높이가 가져가야 하는 나무의 높이보다 클 경우에 나무의 높이를 더 이상 구해도 되지 않으므로 반복문을 멈쳐주었다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법