[백준] 2805.cpp : 나무 자르기

www.acmicpc.net/problem/2805 

2805번: 나무 자르기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<long long int> v;

// 나무들을 다 잘랐을 때 가능한 합이 m 을 넘는지, 못 넘는지
bool check(const long long int& mid)
{
  long long int sum = 0;

  for(int i = 0 ; i < n ; i++)
  {
    // 자른 길이가 0보다 클때만 더해줌
    if(v[i] - mid > 0)
    {
      sum += v[i] - mid;
      // 정렬되어있는 상태이기 때문에, 그냥 앞에서부터 쭉 더했을때 m 보다 크면 가능하다고 판단
      if(sum >= m)
      {
        return true;
      }
    }
  }

  return false;
}

int main(void)
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long int data;
  cin >> n >> m;

  v.reserve(1000000);
  for(int i = 0 ; i < n ; i++)
  {
    cin >> data;
    v.emplace_back(data);
  }
  // 나무들을 정렬해줘서 완전탐색 할 필요 없게
  sort(v.begin(), v.end());

  long long int low = 0;
  long long int high = *(v.end() - 1);
  long long int mid = 0;
  long long int ans = 0;

  // 이분 탐색 시작
  while(low <= high)
  {
    mid = (low + high) / 2;

    // 잘랐을 때 m 이 넘으면
    if(check(mid))
    {
      // 값을 넣어주고 위쪽을 탐색
      if(ans < mid) ans = mid;
      low = mid + 1;
    }
    else // 못 넘으면
    {
      // 아랫쪽을 탐색
      high = mid - 1;
    }
  }
  cout << ans << endl;
}

 

[Try]

1. 이분탐색을 통해 매번 다 잘라내서 합을 구한다. 자르기 전에 나무들을 정렬해놓고 한번 자를때마다 잘라낸 값들을 더해서 비교한다

2. 이분탐색 구현이 잘못됐나?? high = mid - 1 로 옮겨 준 것이 문제가 된 것 같다. 자기 자신도 포함시켜서 검사하기

3. 계속 디버깅용으로 써놨던 출력까지 포함해서 제출하고 있었음

4. 도저히 이해가 안돼서 구글링을 통해 푸신분의 방법이랑 똑같이 했는데 틀렸습니다 ^^ 너무 스트레스받는다

5. 이분탐색 알고리즘을 진지하게 정밀검사 해보았다

6. 엄청난 시도 끝에 결국 틀린 이유는 자료형 때문이었다 ^^ 아니 최대 20억이라 int 오버플로우가 안 날 줄 알았는데 sum 에서 나고

     있었나 보다.

 

[Point]

1. unsigned int 의 경우는 이분탐색 할 때 high 가 -1 로 갈 경우 똑같이 언더플로우 생겨서 틀릴 수 있다.

2. 자료형의 중요성.... 1시간 동안 이가 갈렸다 진짜

 

[More]

1. 이분탐색 과정을 머릿속에 더 깔끔하게 집어넣을 수 있도록 하자