(JAVA) 백준 2805번 - 나무 자르기

문제 링크: https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

풀이

처음에는 브루트 포스를 사용하여 아래와 같이 풀이해 보았다.

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        List<Integer> tmp = new ArrayList<>();
        for (int i = 0; i < n; i++) tmp.add(Integer.parseInt(st.nextToken()));

        int answer = 0;
        long sum;
        while(true){
            sum = 0;
            for(int num : tmp) {
                int diff = num - answer;
                if (diff >= 0) sum += diff;
            }
            if(sum < m) break;
            answer++;
        }
        bw.write(Integer.toString(answer-1));
        bw.close();
    }
}

단순하게 절단기의 높이를 0부터 시작하여 절단한 나무들의 길이의 합을 계산한다. 조건을 만족하지 않는 경우가 될 때까지 1씩 높여가면서 가능한 최댓값을 구하는 방식을 사용해 보았다. 하지만 이 방법을 사용하게 될 시에는 n이 백만 개 정도이기에 위의 n^2의 경우에는 무조건 시간 초과가 발생할 수밖에 없다.

그리고 역시 예상대로 시간초과가 발생했다.

 

그래서 다른 방법을 사용해야만 했는데, 이분 탐색을 사용해서 mid 값을 조절하여 알맞은 절단기의 높이를 구하는 방식을 사용하였다.

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int max = 0;
        int min = 0;
        List<Integer> tmp = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(st.nextToken());
            tmp.add(x);
            if(max < x) max = x;
        }

        while(max > min){
            int mid = (max + min) / 2;
            long sum = 0;
            for(int height : tmp){
                if(height - mid > 0) sum += height - mid;
            }

            if(sum < m) max = mid;
            else min = mid + 1;
        }
        bw.write(Integer.toString(min-1));
        bw.close();
    }
}

시간 복잡도가 nlogn이기에 백만 정도의 n에 대해서는 제한 시간 내에 통과될 수 있다.