백준 나무자르기 문제풀이

문제 

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

2805번: 나무 자르기

 

 

 

문제 접근 방식

나무 길이 trees 에 대해 절단한 나무 길이 합이 적어도 m 이상을 만족시키는 절단기 높이 height의 최댓값을 구하는 문제이다.

이렇게 최댓값, 최솟값을 구하는 문제를 최적화 문제라고 하는데, 이러한 최적화 문제를 푸는 방법 중 파라메트릭 서치라는 기법이 존재한다.

 

최적화 문제를 True, False를 반환하는 함수를 만들고 이분 탐색으로 수를 넣어보면서 조절해 가며 최적의 답을 구하는 방법이다.

 

이 문제의 경우, 아래 decision(height) 라는 함수를 만들고, 이 함수의 height를 이분법으로 탐색을 한다.

decision(height) = 절단기의 높이 height 이상인 나무들을 모두 잘랐을 때, 잘린 나무 길이의 합이 M 이상인지 여부를 반환한다.

 

decision(height)가 True 라면 해당 높이로 잘라도 만족하는 것이므로 높이을 증가해서 잘라보고,

m 미만이라면 높이를 줄여보는 것이다. 이 늘리고 줄이는 방식을 이분탐색으로 진행한다.

 

시간 복잡도

이분법의 시간 복잡도가 O(k) 이고 decision의 시간복잡도가 O(n) 이다.

k의 최댓값이 1e9이고, n의 최댓값이 1e6 이므로 시간내에 동작할 것이다.

 

코드

MAX=int(1e9)

# decision = 절단기의 높이 height 이상인 나무들을 잘랐을 때, 잘린 나무 길이의 합이 M 이 넘는지 여부를 판단한다.
def decision(height):
    total=0
    for tree in trees:
        if tree>height:
            total+=tree-height

    if total >=m:
        return True

    return False


if __name__=='__main__':
    n,m=map(int,input().split())
    trees=list(map(int,input().split()))

    s,e=0,MAX
    answer=0

    # 이분탐색을 통해 절단기의 높이를 조절한다
    # 특정 절단기 높이가 decision 함수를 만족하면 더 큰 높이를 넣어보고,
    # decision 함수를 만족하지 못하면 작은쪽으로 진행을 한다.
    while s<=e:
        mid =(s+e)//2
        if decision(mid) ==True:
            answer=mid
            s=mid+1
        else:
            e=mid-1

    print(answer)

 

 

회고

파라메트릭 서치의 존재를 기억해놓고 최적화 문제가 나왔을 경우 해당 기법을 선택하여 문제를 풀 수 있도록 하자.