JArchive 프로그래밍 일기

문제

나무 자르기 백준 2805

"맞았습니다" 코드

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;

// 2805 나무자르기
long long n, m, num, answer;
vector<long long> v;

void bs(){

  int start = 0;
  int end = *max_element(v.begin(), v.end());
  int mid = 0;

  while(start <= end){
    mid = (start+end)/2;

    long long tempsum = 0;
    for(int i=0; i <n; i++){
      if(v[i]>mid) tempsum += (v[i]-mid);
    }
    if(tempsum >= m){  // 조건 만족시, 
      answer = mid;
      start = mid+1;
    }else{ // 덜 깎아야 함.
      end = mid-1;
    }
  }

  cout << answer;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;

  for(int i = 0; i < n; i++){
    cin >> num;
    v.push_back(num);
  }

  bs();
  return 0;
}

리뷰

나무의 수와 높이가 꽤 크다.
나무는 백만개가 최대.
높이는 10억이 최대.

단순하게 절단기 높이를 0부터 10억까지 반복문으로 검사하기에는 시간이 오래걸린다.
10억 x 100만 이기 때문이다.

따라서 이분탐색으로 절단기의 높이를 찾는다.
이 때, 최소값은 0, 최대값은 나무중에서 제일 긴것을 기준점으로 잡는다.

이분 탐색의 중간값mid로 나무를 절단했을 때,
잘라낸 나무 누적 합(tempsum)이 기준값(m)을 만족시키면 답으로 저장해둔다.
answer = mid;

기준값보다 잘라낸게 더 많으면, 덜 깎아야 하니깐 start = mid+1; 절단기의 높이를 높여야 덜 깎는다.
기준값보다 누적합이 작으면, 더 깎아야 하니까 end=mid-1; 절단기의 높이를 줄여야 더 많이 깎여나간다.

"절단기의 높이를 줄이면, 나무가 더 많이 깎여나가니까 tempsum이 증가한다"
처음에는 이 부분이 헷갈렸었다.