[C++] 백준 BOJ 2805 나무 자르기

문제링크 : https://boj.kr/2805

1. 동적계획법(DP)을 이용한 풀이법 : 시간복잡도 O(N)

나무의 길이가 제일 큰 것부터 시작하여 한단계씩 내려오면서 누적 합이 입력에서 주어진 값보다 클 때까지 구하는 방법으로 풀었다.

입력 받은 값들을 내림차순으로 정렬하고 맨 첫번째 인덱스에 해당하는 값부터 시작하여 1씩 높이를 빼가면서 계산했다.

나무의 높이(arr[N])가 기준 높이(result)보다 높은 부분 까지만 인덱스를 탐색하고 기준 높이 이하(arr[N] - result)가 0 이하인 값들)가 나오면 현재 누적 잘린 나무들의 합이 정답보다 작다면 계속 루프를 진행한다.

이때, 높이를 1씩 빼게되면 현재까지 진행해왔던 나무들의 높이가 각각 1씩 추가되기 때문에 sum += ptr 구문을 넣어 더해줬다.

그림으로 설명하자면 아래와 같이 설명할 수 있다.

회색은 이전 루프에서 누적된 값 (sum)

노란색은 현재 루프에서 누적된 값 (sum += arr[ptr++] - result)

초록색은 다음 루프로 넘어갈 때 추가되는 값 (sum += ptr)

여기서 노란색 ptr은 루프 끝나는 부분의 인덱스이며

초록색 ptr은 루프 시작 부분의 인덱스를 의미한다.

++이 후위연산(postfix)이기 때문에 현재 루프를 탈출하기 전에는 노란색 인덱스, 다음 루프때 ++이 되어 초록색 인덱스가 된다.

(답이 나올 때까지 반복)

// BOJ 2805 나무 자르기
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
 
int main() {
    // freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    int num, legnth;
    cin >> num >> legnth;
    vector<int> arr(num);
    for (int i = 0; i < num; i++)
        cin >> arr[i];
    sort(arr.begin(), arr.end(), greater<int>());
    int sum = 0;
    int result = arr.front() - 1;
    int ptr = 0;
    while (true) {
        while (arr[ptr] - result > 0)
            sum += arr[ptr++] - result;
        if (sum < legnth) {
            result--;
            sum += ptr;
        }
        else {
            break;
        }
    }
    cout << result;
 
    return 0;
}        

2. 이진탐색(Binary Search)를 추가로 적용한 풀이법 : 시간복잡도 O(logN)

위에서 정답을 찾기 위해서 맨 큰 숫자부터 시작하여 1씩 줄여가면서 찾았기 때문에 최악의 경우는 N번을 모두 실행해야 하기 때문에 O(N)임을 알 수 있다.

하지만, 이진탐색 기법을 추가로 적용한다면 정답의 가능성이 있는 부분만 취하고 나머지 절반은 버리는 식으로 계속 탐색을 하기 때문에 탐색 횟수를 훨씬 줄일 수 있다.

// BOJ 2805 나무 자르기
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
 
using namespace std;
 
int main() {
    // freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    int num, length;
    cin >> num >> length;
    vector<int> arr(num);
    for (int i = 0; i < num; i++)
        cin >> arr[i];
    sort(arr.begin(), arr.end(), greater<int>());
 
    int top = arr.front();
    int mid = 0;
    int btm = 0;
    int result = 0;
 
    while (btm < top) {
        long long sum = 0;
        mid = (top + btm) / 2;
        for (int i = 0; i < num && arr[i] - mid > 0; i++)
            sum += arr[i] - mid;
        if (sum < length) {
            top = mid;
        } else {
            result = mid;
            btm = mid + 1;
        }
    }
    cout << result;
 
    return 0;
}        

DP를 적용하지 않고 풀어도 수행시간은 의미있는 수치만큼의 차이는 없다.

// BOJ 2805 나무 자르기
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    // freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    int num, length;
    cin >> num >> length;
    vector<int> arr(num);
 
    int top = 0;
    int mid = 0;
    int btm = 0;
    int result = 0;
    
    for (int i = 0; i < num; i++) {
        cin >> arr[i];
        top = max(top, arr[i]);
    }
    
    while (btm < top) {
        long long sum = 0;
        mid = (top + btm) / 2;
        for (int i = 0; i < num; i++)
            if(arr[i] - mid > 0)
                sum += arr[i] - mid;
        if (sum < length) {
            top = mid;
        } else {
            result = mid;
            btm = mid + 1;
        }
    }
    cout << result;
 
    return 0;
}        
 

수행시간 비교

1. DP

2. 이진탐색