백준 2805번 : 나무 자르기

나무 자르기

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

 

이 문제의 핵심은 이분탐색이다.

Code

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    long long num_tree, m;
    cin >> num_tree >> m;
    vector<int> trees(num_tree);

    for(int i = 0; i < num_tree; i++) cin >> trees[i];
    sort(trees.begin(), trees.end());

    long long min = 0;
    long long max = trees[num_tree-1];
    long long result = 0;

    while(min <= max){
        long long mid = min + (max - min) / 2;
        long long sum = 0;
        for (int i = 0; i < num_tree; i++) {
            if (trees[i] > mid) {
                sum += trees[i] - mid;
            }
        }
        if (sum >= m) {
            result = mid; 
            min = mid + 1;
        } else {
            max = mid - 1;
        }
    }
    cout << result << endl;
    return 0;
}

 

입력 받기

long long num_tree, m;
cin >> num_tree >> m;
vector<int> trees(num_tree);

for(int i = 0; i < num_tree; i++) cin >> trees[i];

입력 받는 숫자의 크기에 따라 자료형에 유의한다.

long long 타입 선택.

출처 : https://sweetnew.tistory.com/16

정렬 하기

sort(trees.begin(), trees.end());

최솟값과 최댓값을 기준으로 이분 탐색을 하기 때문에 정렬이 필요하다.

 

이분 탐색

long long min = 0;
long long max = trees[num_tree-1];
long long result = 0;

while(min <= max){
    long long mid = min + (max - min) / 2;
    long long sum = 0;
    for (int i = 0; i < num_tree; i++) {
        if (trees[i] > mid) {
            sum += trees[i] - mid;
        }
    }
    if (sum >= m) {
        result = mid; 
        min = mid + 1;
    } else {
        max = mid - 1;
    }
}
cout << result << endl;
return 0;

min이 max를 추월할 때 while을 탈출한다.

이는 조건을 만족하기 위한 최댓값을 만족하기 위해서다.

 

이후 조건에 따라 나무의 합을 정해진 값과 비교하며 범위를 좁혀간다.

깨달은점

• 항상 입력 데이터의 크기를 고려하여 자료형을 고르자.
• 정확한 종료 조건을 고려하자.
• 탐색범위 업데이트시 mid를 포함하지 않도록 주의하자.
  mid를 포함하여 업데이트하면 무한루프에 빠질 수 있다.
• 이분 탐색 디버깅의 핵심 부분은 
  
  • mid 값과 탐색 범위 확인
  • 종료조건 확인