[Python] BOJ/백준 2805번 나무 자르기

[문제]

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

[풀이]

같은 코드여도 pypy3로 하면 맞는데 python3로 하면 다 시간 초과 오류 떴다..

처음에는 brute force로 푸는 줄 알고 우왕 쉽다 하면서 풀었는데 시간 초과가 떠서 이건 이렇게 간단하게 풀 문제가 아니라는 걸 직감했다. -> 이분 탐색으로 풀어야 한다

 

1. 가장 짧은 나무의 길이를 1을 start로, trees 중 가장 큰 값을 end로 지정한다.
2. start가 end 이하일 동안 반복한다.
3. mid는 start와 end 중간이며, 갖고 있는 모든 트리 값을 mid로 뺐을 때 총 몇 cm의 트리가 남는지 total에 저장한다.
4. total 조건문
   1. total 값이 want 이상일 경우 start를 mid+1로 두고 다시 while문을 반복한다.
   2. total 값이 want 이하일 경우 end를 mid-1로 두고 다시 while문을 반복한다.
5. 위의 방법으로 끝까지 (start와 end가 같아지는 지점) 구했을 때 반복문을 탈출한다.
6. 결괏값인 end를 출력한다.

 

[코드]

- 시간 초과(brute force)

import sys

if __name__ == '__main__':
    n, want = map(int, sys.stdin.readline().split())
    trees = sorted(list(map(int, sys.stdin.readline().split())))

    for i in range(trees[-1], 0, -1):
        temp = 0
        for j in trees:
            if i >= j:
                pass
            else:
                temp += (j - i)
        if temp == want:
            print(i)
            break

 

- 제출 코드(binary search)

import sys

if __name__ == '__main__':
    n, want = map(int, sys.stdin.readline().split())
    trees = list(map(int, sys.stdin.readline().split()))
    start, end = 1, max(trees)

    while start <= end:
        mid = (start + end) // 2

        total = 0   # 잘린 나무의 합
        for i in trees:
            if i >= mid:    # mid보다 높이가 크면 잘림
                total += i - mid
        if total >= want:   # 원하는 높이이거나 더 많이 잘렸으면
            start = mid + 1
        else:   # 원하는 높이보다 덜 잘렸으면
            end = mid - 1
    print(end)