[백준 2805번] 나무 자르기

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

 

수정전

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
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));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

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


        List<Integer> tree = new ArrayList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            tree.add(Integer.parseInt(st.nextToken()));
        }
        int answer = 0;
        int compare = 0;
        Collections.sort(tree, Collections.reverseOrder());
        int begin = tree.get(0);
        int last = tree.get(tree.size() - 1);

        int cnt =0;
        while (compare !=M) {
            answer = (begin + last) / 2;

            compare = 0;
            for (int i = 0; i < tree.size(); i++) {
                if (tree.get(i) > answer) {
                    compare += (tree.get(i) - answer);
                }else{
                    break;
                }
            }

            if (compare > M) {
                last = answer;
            } else if (compare < M) {
                begin = answer;
            }

        }

        System.out.println(answer);
    }
}

 

수정후

package datastructure;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

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


        int[] tree = new int[N];
        int max = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            tree[i] = Integer.parseInt(st.nextToken());
            if (tree[i] > max) {
                max = tree[i];
            }
        }
        int answer = 0;
        int left = 0;
        int right = max;


        while (left <= right) {
            int mid = (left + right) / 2;
            long total = 0;
            for (int i = 0; i < tree.length; i++) {
                if (tree[i] > mid) {
                    total += tree[i] - mid;
                }
            }

            if (total >= M) {
                left = mid + 1;
                answer = mid;
            } else if (total < M) {
                right = mid - 1;
            }

        }

        System.out.println(answer);
    }
}

 

 

큰 값, 작은 값 합쳐서 중간값 구한 후 계속해서 중간 값을 구하면 해결할 줄 알았으나.... 시간 초과!!! 문제를 자세히 읽어보니 필자가 잘못 읽었다... ㅎㅎㅎ 적어도 M 그 뜻은 M 이거나 M보다 커야 된다. 그때 최댒값을 구하면 된다. 

 

따라서 left와 right로 비교를 해준뒤 최대값을 향해서 루프를 돌면 되는 간단한 문제이다. 참고로 left +1, right -1을 해주는 이유는 만약 left가 12이고 right 13일때 계속 무한루프에 빠질 수 있기 때문이다. 그래서 각각 더해주고 뺴줘야지 성립이 된다.