백준 파이썬 2805번

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

1. 완전 탐색(Brute Force)

(시간 초과)

import sys

# 나무 한 줄을 기준 높이로 자를 때 가져갈 수 있는 나무 길이 합
def cut(limit, tree):
    cutLength = 0
    for i in tree:
        if i > limit: cutLength += i - limit
    return cutLength


treeLength = 0
N, M = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))

# 완전 탐색
for i in range(max(tree) - 1, -1, -1):
    # cut의 결과가 M보다 크거나 같을 때 결과값 갱신
    if M <= cut(i, tree):
        treeLength = i
        break
print(treeLength)

나무 리스트에서 가장 높은 나무의 높이를 h라하자.
h-1부터 cut을 실행해서 최초로 M보다 크거나 같은 값이 나온다면 그 높이가 최댓값이 된다.
이 작업을 높이 0으로 cut할 때까지 실행한다.

그러나, 시간복잡도가 O(N x H)가 되기 때문에
최악의 경우로 N = 1_000_000, H = 1_000_000_000이 되면
연산횟수가 너무 커져버린다.

다른 방법을 찾아야한다.

2. 이분 탐색

import sys


def cut(limit: int, tree: list) -> int:
    cutLength = 0
    for i in tree:
        if i > limit: cutLength += i - limit
    return cutLength


tree_length = 2_000_000_000
N, M = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))

# 오름차순 정렬
tree.sort()

# 이분 탐색 시작
# left는 최솟값인 0, right는 나무 리스트의 최댓값
left = 0
right = tree[len(tree) - 1]
while left <= right:
    mid = (left + right) // 2
    
    # cut 실행
    res = cut(mid, tree)
    
    # M보다 크거나 같은 값이 나오면 갱신
    # left를 조정, 즉, 잘라야 할 나무 수를 줄여본다
    if res >= M:
        left = mid + 1
        tree_length = mid
        
    # M보다 작으면 right 조정
    #즉, 잘라야 할 나무가 더 필요
    else:
        right = mid - 1
print(tree_length)

완전 탐색으로 풀기 힘든 문제는 이분 탐색을 생각해보자.

이것으로 solved.ac 클래스 2 문제를 모두 해결했다.