[백준] 2805번 나무 자르기

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다)

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을 넘기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

 

이제 이분 탐색이 거의 적응한 느낌이 들었다. 이 문제는 틀렸는데 알고 보니 범위 때문에 틀렸다.

 

#include <bits/stdc++.h>
using namespace std;

long long tree[1000001];
int main(void) {
  long long n,m;
  cin >> n >> m;

  for(int i = 0; i<n;i++) {
    cin >> tree[i];
  }
  sort(tree, tree+n);

  int left = 1;
  int right = tree[n-1];
  int result = 0;

  while(left <= right) {
    long long mid = (left+right)/2;
    long long slice = 0;
    for(int i = 0; i<n;i++) {
      int temp = tree[i] - mid;
      if (temp > 0) {
        slice += temp;
      }
    }

    if (slice >= m) {
       result = mid;
       left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  cout << result << "\n";
}

문제를 설명하면 예제에서

 

나무 4 그루

 

20 15 10 17 이런식으로 되어 있고,  상근이가 가져가야할 나무의 길이는 총 7이라고 할때,

최대값을 물어보는 문제다.

 

가장 먼저 생각할 수 있는건 일단 빼보자 그러면 답이 나올지도 모른다.

13 8 3 10 ??????? 답이 나오지 않는다.

 

지문에서도 알 수 있듯이 7m을 가져가려면 15m를 남겨두고 자르라는 것 같다.

그러니까 전부 15m로 일정하게 잘라주면 된다.

그러면 20-15 = 5, 15,10은 15보다 작거나 같으므로 패스 17-15 = 2 이렇게 해서 총 7이 나온다.

 

그런데 이게 어떻게 가능할까?

우리가 생각할 수 있는건 어떻게 자르냐라고 생각한다. 

최솟값으로 자를지, 최댓값으로 자를지.. (물론 답은 아니다. 이해를 돕기 위한 거다.)

 

최솟값은 10이다. 그런데 굳이 10으로 자를 이유는 전혀 없다. 왜냐하면 10m보다 작은 값으로도 자를 수 있기 때문이다. 그러면 자를 수 있는 최솟값은 1이다. 따라서 최솟값은 10이 아니라 1이된다.

 

그럼 최댓값은? 당연히 20이다. 이건 왜 당연하냐면 21씩 자를 수 없기 때문이다.

 

그러면 우리는 1부터 20까지 나무를 자를 수 있다. 이제 1부터 20까지 나무가 얼마나 잘라지는지 계산하면 된다.

마치 

19 14 9 18...

0 0 0 0 ... 이런식이다.

근뎅 애초에 나무를 얼마나 자를지에 대한 조건도 추가 되었기 때문에 이를 계산해주면 (7)

19+14+9+18 ㄷㄷ 40이 넘어가는 숫자다. 물론 이것도 정답이 될 수도 있겠지만... 애석하게도 여기서는 답이 아니다.

 

그럼 어떻게 계산해야 할까?

간단히 생각하면 중간부터 생각하면 된다. 잘 모르지만 log시간내에 계산이 가능하다고는 한다.

 

지금부터 1부터 20까지 번호를 적어보겠다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  이런식으로... 그럼 중간을 체크 해보자.

                        o                                             10에 체크 되었다. 그럼 계산해보자.

 

20 15 10 17 -> 10 5 0 7 이 된다. 이를 더하면 22가 되는데 아직도 값이 크다. 왜냐하면 내가 구해야할 값은 7이기 때문이다. 그러면 왼쪽은 무조건 정답이 아니니 오른쪽으로 가야한다. 왜 왼쪽이 아닌 이유는

아까 1을 계산했을떄 40이 넘는 숫자가 작성되었다. 그런데 10을 계산했을 때는 값이 줄었다 하지만 답이 아니다. 그렇다는 소리는 1부터 9까지는 전부 답이 아니기 때문에 굳이 계산할 이유는 없다.

 

그러면 값을 어떻게 추가해야할까?

최솟값을 1에서 11로 변경시켜야한다. 이건 간단히 말해 중간값에서 1을 앞으로 간값을 뜻한다. 이런식으로 계속 진행 하면

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

o                                                                o

                       O

                            o                                    o

                                             O

                                                  o              o

                                                        O 

                                                              o  o

                                                              O

 

 뭐 대충 이런 그림이 된다. 귀찮아서 그림은 그리지 않았지만. 아무튼 이렇다.

그러면 큰 동그라미들만 계산해도 답이 나온다. 답이 나오는 이유는 이값으로 빼기 때문이다.

따라서 답은 15!  여기는 조금 생략 했다. 

 

 

이런게 이분 탐색이라고 한다.!