[JAVA]BOJ 2805, 나무 자르기

심하게 삽질 한 문제!!! 난 바보다...

 

이진탐색을 한다. 문제에 있는 예시처럼 10 15 17 20 배열이 있다면, 0 ~ 20으로 이진탐색을 한다. 처음에는 mid가 10이 됐다가.. 값 크기 차이를 보고 앞부분을 탐색하거나 뒷부분을 탐색한다.

 

이진탐색 쓰기로 정했을때 그 생각을 못하고 배열자체를 이진탐색해서 정확하게 찾은 경우, 못찾은경우에 mid들을 비교해서 1개씩 비교하고.. 어쩌고.. ㅎ.. 심지어 제일 처음에 풀때는 브루트포스로 풀었고 다른 예시는 다 적용이 되나 나무 크기가 중복되는 경우(10 10 10 <- 이런식으로.. )에 해결을 못해서 버렸다. 그리고 이진탐색했는데 또 이상하게하고.. 시간만 왕창썼다ㅎㅎㅎ.. 암튼 해결~!

 

1. 입력받고 정렬 -> 이진탐색 해야되니까..

2. 이진탐색으로 적절한 값 찾기

3. 출력하기

 

1. 3. 은 생략.. 2.만 추가설명

 

2. 이진탐색으로 적절한 값 찾기

위에서 말한대로 0부터 제일 큰 나무 높이를 이용해 이진탐색을 한다. 재귀를 이용한 이진탐색이다. 

나무의 합을 구할때 int범위를 넘어가므로 합은 long으로 선언해야 한다.

public static int binarySearchRecursion(int[] trees, int M, int low, int high) {
    int mid;
    long wood;

    if (low <= high) {
        mid = (high + low)  / 2;
        wood = getWoodLength(trees, mid);

        if (wood == M) // 자른 나무들이랑 필요한 나무가 동일하지 않을때 -> 탐색은 끝났는데 정확한 답이 없음
            return mid;
        else if(low == high)  // 여유있게 잘라야하므로 현재 자른 나무이 더 큰 경우는 바로 리턴, 작은 경우는 -1 해서 리턴
            return wood > M ? mid : mid - 1;
        else if (wood > M)
            return binarySearchRecursion(trees, M, mid + 1, high);
        else
            return binarySearchRecursion(trees, M, low, mid - 1);
    }

    return -100; // 구색갖추기용, 절대 실행되지 않는 코드
}

if(wood == M) .. 과 else if(low == high) .. 부분이 실제 답을 리턴하는 부분이다.

• if(wood == M) 은 필요한 나무와 자른 나무(wood)가 동일할때이다. 4 7 / 10 15 17 20 에 알맞는 예시이다.
• else if(low == high) 는 필요한 나무와 자른 나무(wood)가 다를때이다. 4 8 / 10 15 17 20, 4 4 / 10 15 17 20 경우에 적용되는 부분이다.

그 아래 조건들은 그냥 이진탐색 코드이다. 설명은 생략..

 

아래는 반례들이다. 이진탐색을 할때 어떤 값이 들어가는지 다 계산해봤다.. 모든 예외를 다 포함한 예시이다.

4 7
10 15 17 20 -> 0, 20, 10(22) -> 11, 20, 15(7)
15

4 5
10 15 17 20  -> 0, 20, 10(22) -> 11, 20, 15(7) -> 16, 20, 18(2) -> 16, 17, 16(5)
16

4 3
10 15 17 20 -> 0, 20, 10(22) -> 11, 20, 15(7) -> 16, 20, 18(2) -> 16, 17, 16(5) -> 17, 17, 17(3)
17

4 8
10 15 17 20 -> 0, 20, 10(22) -> 11, 20, 15(7) -> 11, 14, 12(16) -> 13, 14, 13(13) -> 14, 14, 14(10)
14

4 4
10 15 17 20 -> 0, 20, 10(22) -> 11, 20, 15(7) -> 16, 20, 18(2) -> 16, 17, 16(5) -> 17, 17, 17(3)
16

 

---

아래는 전체 코드이다.

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

public class BOJ2805 {
    public static long getWoodLength(int[] trees, int cutHeight) {
        int i;
        long sum = 0;

        for (i = trees.length - 1; i >= 0; i--)
            if (trees[i] > cutHeight)
                sum += trees[i] - cutHeight;
        return sum;
    }

    public static int binarySearchRecursion(int[] trees, int M, int low, int high) {
        int mid;
        long wood;

        if (low <= high) {
            mid = (high + low)  / 2;
            wood = getWoodLength(trees, mid);

            if (wood == M) // 자른 나무들이랑 필요한 나무가 동일할때
                return mid;
            else if(low == high)  // 자른 나무들이랑 필요한 나무가 동일할때
                return wood > M ? mid : mid - 1; // 여유있게 잘라야하므로 현재 자른 나무이 더 큰 경우는 바로 리턴, 작은 경우는 -1 해서 리턴
            else if (wood > M)
                return binarySearchRecursion(trees, M, mid + 1, high);
            else 
                return binarySearchRecursion(trees, M, low, mid - 1);
        }
        
        return -100; // 구색갖추기용, 절대 실행되지 않는 코드
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, M, i;
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int[] trees = new int[N];

        st = new StringTokenizer(br.readLine());
        for (i = 0; i < N; i++)
            trees[i] = Integer.parseInt(st.nextToken());

        // 정렬
        Arrays.sort(trees);
		
        // 출력
        System.out.println(binarySearchRecursion(trees, M, 0, trees[N - 1]));
    }
}

 

반례들

4 7
10 15 17 20
15

4 5
10 15 17 20
16

4 4
10 15 17 20
16

4 3
10 15 17 20
17

4 8
10 15 17 20
14

 

2 10
5 5
0

2 3
5 5
3

50 2000000000
123645687 718613219 882279696 727553593 64522456 358750471 346246716 129205648 997536909 515997747 62870161 582298474 930000316 647480048 597704111 957107404 382436612 838076383 445032056 373747206 780008424 80837217 564255977 299280004 900171238 886005228 842346920 730834225 85600993 246514888 989327098 146130505 63059251 478390453 310502851 669474177 144453075 771507026 931973314 329024410 649167016 511733274 41481711 133698733 739465061 409663874 751169443 516403718 226012958 209515204
728520579

5 10
8 8 8 8 8
6

12 2000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
833333333