BOJ S2 2805 나무 자르기 JAVA

2805번: 나무 자르기

---

문제 읽기

이 문제는 일단 입력 값이 너무 컸기 때문에 바로 이분 탐색을 써야 겠다고 생각이 들었다. 입력 값을 한번 보자.

• 나무의 수 N : 1~1,000,000(백만)
• 필요한 나무 길이 M : 1 ~ 2,000,000,000(이십억)
• 나무의 높이 : 0~1,000,000,000(십억)

만약 완전 나이브하게 풀이한다면, 나무를 자를 높이를 0에서부터 십억까지 1씩 증가시키면서, N개의 나무를 다 잘라보고, 총합이 필요한 나무 길이를 충족시키면 답을 리턴하는, 그런 방식이 있다.

 

하지만 이렇게 하면 시간 복잡도가 최악의 경우 10억 * 백만이라는 엄청난 시간이 나오고, 따라서 이건 불가능하다.

 

그래서 나무를 자를 높이를 구할 때 이분 탐색을 적용한다!

---

문제 풀기

전체적인 흐름은 비슷하지만, 이분탐색을 적용하면 다음과 같이 빠르게 구할 수 있다.

1. 나무를 자를 높이를 이분 탐색을 통해 설정한다.
   1. 초기값 설정
      1. start : 0
      2. end : 10억
2. mid = (start + end) / 2 값을 구해 나무를 자른다
   1. 자른 값이 내가 구하는 값을 충족한다면(M보다 크다) 자를 높이를 더 올려도 된다는 뜻이므로,
      1. 현재 mid값으로 result 값을 업데이트 한 후,(절단기 높이의 최댓값을 구하므로)
      2. binarySearch(mid+1, end)를 탐색한다.
   2. 자른 값이 내가 구하는 값을 충족하지 못한다면(M보다 작다) 자를 높이를 더 내려야 한다는 뜻이므로,
      1. binarySearch(start, mid)를 탐색한다.
3. result값을 출력한다.

---

실수한 부분

자료형 : 2% 틀렸습니다

해당 문제는 자료형이 int 범위에 아슬아슬하다. int는 보통 20억, 그 이상은 long을 써야 한다고 보면 되는데, 해당 문제에서 나무의 높이가 최대 10억이고, 나무의 개수가 백만 개이기 때문에 나무의 높이를 더하다 보면 int 범위는 거뜬히 넘어선다.. 해당 부분을 long으로 바꾸어야 한다.

 

binarySearch의 lower bound와 upper bound : 36% 틀렸습니다

처음에 binarySearch를 호출할 때 최소 바운드와 최대 바운드를 다음과 같이 입력 받은 나무의 높이 배열에서 최솟값, 최댓값을 구해서 넣어주었다. 이렇게 하는 게 더 효율적이라 생각했기 때문이다.

        int maxH = 0;
        int minH = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++){
            trees[i] = Integer.parseInt(st.nextToken());
            maxH = Math.max(maxH, trees[i]);
            minH = Math.min(minH, trees[i]);
        }

        binarySearch(minH, maxH);

 

하지만 이렇게 하니까 계속 36퍼센트 쯤에서 틀리게 나왔었다.

 

반례를 찾아보다가 다음과 같은 글을 발견했다.

글 읽기 - right 범위 설정시 실패하는 이유가 궁금합니다.

# input
10 1
600000000 600000000 600000000 600000000 600000000 600000000 600000000 600000000 600000000 600000000

# ans
599999999

 

이 반례를 넣어보면 알 수 있을 것인데, 나는 binarySearch 함수에서 종료 조건을 (start ≥ end)로 설정했다. 즉, 입력 받은 배열에서 maxH와 minH 값이 같아버리면, 이분 탐색을 시작도 하기 전에 리턴 해버리는 것이다..! 이 때문에 위 반례의 답이 0으로 나왔었고, lowerbound는 0, upper bound는 10억으로, 즉 입력 값의 범위로 설정 해주어 해결할 수 있었다.

---

코드

package ps.ㄱSolving;

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

public class BOJ_S2_2805_나무자르기 {
    static int N, M;
    static int[] trees;
    static long maxHeight = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        trees = new int[N];
        st = new StringTokenizer(in.readLine());
//        int maxH = 0;
//        int minH = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++){
            trees[i] = Integer.parseInt(st.nextToken());
//            maxH = Math.max(maxH, trees[i]);
//            minH = Math.min(minH, trees[i]);
        }

        binarySearch(0, 1000000000);
        System.out.println(maxHeight);
    }

    private static void binarySearch(int minH, int maxH) {
        if (minH >= maxH) return;

        int mid = (minH + maxH) / 2;
        long tree = getTree(mid);
//        System.out.println(mid + " " + tree);
        if (tree >= M){
//            System.out.println(mid);
            //더 위로 올려도 된다
            maxHeight = Math.max(maxHeight, mid);
            binarySearch(mid+1, maxH);
        }
        else{
            //내려야 한다
            binarySearch(minH, mid);
        }

    }

    private static long getTree(int cutting) {
        long amount = 0;
        for (int tree : trees){
            int cut = tree - cutting;
            if (cut > 0) amount += cut;
        }
        return amount;
    }
}