백준 2805 나무 자르기 (JAVA 자바 풀이)

백준 2805 나무 자르기 (JAVA 자바 풀이)

 

---

 

 

 

문제 

 

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

 

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

 

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

 

입력

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

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

출력

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

 

 

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

2805번: 나무 자르기

 

---

 

💡 풀이 과정 

 

Parametric Search 를 이용한 문제 

 

먼저 정리하고 헷갈리지 않는 개념은 다음과 같다.

- 절단기 높이가 높아질 수록 가져갈 수 있는 양이 적어진다.

- 절단기 높이가 낮아질 수록 가져갈 수 있는 양이 많아진다.

 

5 21 

4 42 40 25 46 

케이스를 보면 어떻게 될까? 

 

36으로 하면 20이 되므로 원하는 값보다 작아진다. 

35로 하면 가져갈 수 있는 나무의 합이 23이 되므로 정답이 된다. 

 

여기서 생각해볼 또 하나의 개념은 다음과 같다. 

- 내가 가져갈 수 있는 나무의 합이 항상 일치하지는 않는다 -> 크거나 같을 수 있다. 

 

 

 

 

어떤 높이 x에 대해서 생각해보면 가장 높은 높이부터 생각해보자. 

제일 높은 높이는 0일 것이다. 

거기서부터 절단기 높이를 낮추면 가져가는 양이 많아지고

어떤 높이 x를 찾았을 때 그때 최초로 가져갈 수 있는 양이 있는 높이 x가 정답이 될 것이다. 

 

 

 

 

 

이때 모든 높이를 볼 수 없으므로 전체 탐색을 하면 시간초과를 받게 된다.

 

여기서 사용할 수 있는 것이 파라메트릭 서치이다. 

 

x를 기준으로 어떤 determine 함수를 작성한다고 해보면 x 이하의 높이는 D(h)가 true, D(h) 는 false를 리턴하도록 한다. 

 

왜냐하면 어떤 경계값 x를 기준으로 높아지면 내가 가져갈 수 있는 양이 적어지고 낮아지면 많아지기 때문이다. 

 

public static boolean isPossible(int[] trees, int cutHeight, int thresholdHeight) {
   long sum = 0;
   for (int tree : trees) {
      if (tree > cutHeight) {
         sum += tree - cutHeight;
      }
   }
   return sum >= thresholdHeight;
}

 

모든 나무에 대해서 내가 지정한 값과 비교를 하면서 절단하고 이를 sum 한다. 

그 합이 내가 원하는 만큼보다 크거나 같으냐를 판단한다. 

 

이 함수의 시간 복잡도는 모든 나무를 돌므로 O(n)이 된다.  

 

- sum이 M보다 작다면, 저 잘라내야 한다 -> 그래야 더 많이 잘라낼 수 있으므로 

- sum이 M보다 크거나 같으면 답의 후보가 된다. -> 답을 갱신하고 더 높은 M이 가능한지를 조사한다. 

 

즉 true라면 점점 x의 범위를 높여 나간다. 

 

조사해야 하는 값은 cutHeight가 되므로 원하는 조사 값의 최 하단을 0으로, 가장 높은 부분을 문제에서 주어진 최대값으로 설정하면 l =0, r = 1,000,000,000(1000000000)이다. 

 

 

int l = minTreeHight;
int r = maxTreeHight;
int answer = -1;

while (l<=r){
   int m = (l+r) /2 ;
   if (isPossible(trees, m, treeLengthInNeed)){
      answer = m;
      l = m +1;
   } else{
      r = m-1;
   }
}

 

중앙 값에 대해서 판정 함수를 반복하면서, 내가 원하는 값을 가져갈 수 있다면 -> 답이 된다.

동시에 answer는 갱신되고, 문제는 더 높은 범위도 답이 될 수 있으므로 l을 올려서 범위를 좁혀준다. 

없다면 절단기는 낮아져야 하므로 r은 올라가도록 한다.

 



문제에서 무조건 가져갈 수 있다고 하였으므로 answer는 무조건 한번 갱신이 될 것이다. 따라서 아무 값이나 초기값으로 해도 된다. 

 

전체 시간 복잡도를 살펴보자. 

 

10억 범위에 대해서 log2H만큼 탐색을 한다. (이분 탐색 log2n) 

이때 isPossible 함수의 시간 복잡도는 O(N)이므로 

-> O(N * logH) 

 

백만 x 30 -> 3천만 정도의 연산이 예상된다. 

 

 

 

 

 

 

 

💡 코드 구현

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {


   public static void main(String[] args) throws IOException {

      BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

      // BufferedReader bufferedReader = new BufferedReader(new FileReader("input.txt"));

      StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      int treeCounts = Integer.parseInt(stringTokenizer.nextToken());
      int treeLengthInNeed = Integer.parseInt(stringTokenizer.nextToken());

      stringTokenizer = new StringTokenizer(bufferedReader.readLine());

      int[] trees = new int[treeCounts];
      while(treeCounts-->0){
         trees[treeCounts] = Integer.parseInt(stringTokenizer.nextToken());
      }

      // 1. 절단기 높이의 탐색 범위를 정한다.
      // 2. 임의의 절단기 높이에 대해
      //   2-1. 원하는 만큼 나무를 가져갈 수 있다면 높이를 높인다.
      //   2-2. 원하는 만큼 가져갈 수 없다면 높이를 낮춘다.
      // 3. 원하는 만큼 가져갈 수 있던 높이 최대값을 출력한다.

      int l = 0;
      int r = 1000000000;
      int answer = -1;

      while (l <= r) {
         int x = (l + r) / 2;
         if (isPossible(trees, x, treeLengthInNeed)) {
            answer = x;
            l = x + 1;
         } else {
            r = x - 1;
         }
      }
      System.out.println(answer);

   }

   public static boolean isPossible(int[] trees, int cutHeight, int thresholdHeight) {
      long sum = 0;
      for (int tree : trees) {
         if (tree > cutHeight) {
            sum += tree - cutHeight;
         }
      }
      return sum >= thresholdHeight;
   }

}

 

 

 

 

---

 

참고자료: 패스트캠퍼스 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java