[백준] 2805 - 나무 자르기

아래는 시간초과한 코드다. 매우 큰 수가 입력되어 결국엔 overflow로 인해서 정상적인 값이 나오지 않았고, Long으로 변경하자마자 시간초과 에러가 발생했다. 정석대로 이분 탐색으로 진행해야 한다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        long M = Long.parseLong(st.nextToken());

        int[] arr = new int[N];
        long max = 0;
        long min = Integer.MAX_VALUE;

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        long saw = 0;
        saw = max - M;

        if(saw < 0) {
            saw = 0;
        }
        while(true) {
            long sum = 0;
            for(int i=0; i<N; i++) {
                if(saw < arr[i]) {
                    sum += arr[i] - saw;
                }
            }
            if(sum < M) {
                break;
            }
            saw++;
        }
        System.out.println(saw - 1);
    }
}

 

이분탐색 정석으로 풀었다.

마지막의 start, end를 바꾸는 부분에서 sum == M일 경우에 start를 올리는게 계속 이해가지 않았다.

합이 M(내가 가져가고 싶은 최소 나무의 길이)와 동일할 때, 아직 start와 end 교차가 되지 않았을 수 있다. 이 때 mid 값을 반환하면 일부의 케이스에는 맞지만, 결국 내가 원하는 건 절단기 높이의 최대 값이므로 'end'를 출력하는게 목표이다.

최소 나무 길이를 만족했으므로, end를 줄이게 되면 나무 길이가 더 늘어나기 때문에 다시 줄이는 방향으로 하다보면 정답에 수렴하게 된다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        long M = Long.parseLong(st.nextToken());

        int[] trees = new int[N];
        st = new StringTokenizer(br.readLine(), " ");

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

        long start = 20;
        long end = 40;
        while (start <= end) {
            long mid = (start + end) / 2;
            long sum = 0;
            for (int i = 0; i < N; i++) {
                if (trees[i] > mid) {
                    sum += trees[i] - mid;
                }
            }
            System.out.println("start = " + start);
            System.out.println("mid = " + mid);
            System.out.println("end = " + end);
            System.out.println("sum = " + sum);
            System.out.println();

            if (sum >= M) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }

        }
        System.out.println(end);
    }
}

 

 

조금 다른 문제지만 동일한 컨셉이다.

 

나무가 예상보다 작을경우에는 무조건 end를 줄여 -> mid를 낮춰야 한다.

나무가 예상보다 크거나 같을때에는 가져갈 양의 조건을 만족했으니 -> mid를 최대한 높이는게 목표이다. 

따라서 result를 mid로 우선 갱신한 후, mid를 높이기 위해 start를 낮춰 -> mid를 높게한다.

start가 end를 뛰어넘을 경우 while문을 빠져나가므로, 최종 갱신된 result가 답이된다.