[백준] 2805번 나무 자르기 (C++) - binary search

문제

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

2805번: 나무 자르기

코드

잘못된 코드

#include <iostream>
#include <vector>

using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> trees;
  int max = 0;
  for(int i=0; i<n; i++){
    int th;
    cin >> th;
    trees.push_back(th);
    if(max < th){
      max = th;
    }
  }

  int start = 0;
  int end = max;

  while(start <= end){
    int mid = (start+end)/2;
    long long int sum = 0;
    for(int h: trees){
      if(h > mid){
        sum += h-mid;
      }
    }
    // 문제 코드
    if(sum == m){
      cout << mid;
      break;
    }
    else if (sum > m){
      start = mid+1;
    }
    else{
      end = mid-1;
    }
  }
}

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> trees;
  int max = 0;
  for(int i=0; i<n; i++){
    int th;
    cin >> th;
    trees.push_back(th);
    if(max < th){
      max = th;
    }
  }

  int start = 0;
  int end = max;
  int result = 0;

  while(start <= end){
    int mid = (start+end)/2;
    long long int sum = 0;
    for(int h: trees){
      if(h > mid){
        sum += h-mid;
      }
    }
    if(sum >= m){
      result = mid;
      start = mid+1;
    }
    else{
      end = mid-1;
    }
  }
  cout << result;
}

정리

처음에 brute force방법으로 풀었는데 역시나 예상했듯이 '시간초과'가 나왔다.

그래서 시간복잡도를 줄이기 위해 이진탐색 방법으로 풀었는데 '틀렸습니다'가 나왔다. 그 이유는 나는 모든 경우에서 나무 높이의 합이 항상 m으로 나올 것이라고 생각했기 때문이었다.

예를 들어 문제 예시에서 보면 20 15 10 17의 경우 15를 기준으로 잘랐을 때 나무 높이의 합이 7로 딱 떨어져 나온다. 하지만 20 15 10 18의 경우에는 8이 나온다. 이 경우에는 14를 기준으로 잘랐을 때의 나무 높이의 합(10)보다 15를 기준으로 잘랐을 때의 나무 높이의 합이 m에 더 가깝기 때문에 15를 출력해야 한다.

그래서 위 두번째 코드처럼 sum이 m보다 크거나 같을 때 result라는 변수에 저장을 해두는 방법으로 이 문제를 해결할 수 있다.

 

또한 이 문제에서는 sum을 long long으로 선언하는 것도 중요하다. sum이 최대로 나올 경우를 생각해보면 1,000,000 * 1,000,000,000 = 1,000,000,000,000,000이다. 따라서 int 대신 long long을 선언 해야 한다. 

 

int (4byte) → -2,147,483,648 ~ 2,147,483,647

long long (8byte) →-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

참조

https://tooo1.tistory.com/123

https://hwan-shell.tistory.com/218

https://2jinishappy.tistory.com/66