문제

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

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class 나무_자르기 {
    public static void main(String[] args) throws IOException {
        try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            long[] nm = convertStringArrayToLongArray(br.readLine().split(" "));

            long m = nm[1];

            long[] trees = convertStringArrayToLongArray(br.readLine().split(" "));

            long answer = solution(trees, m);

            System.out.println(answer);
        }
    }

    private static long[] convertStringArrayToLongArray(String[] args) {
        long[] array = new long[args.length];
        int i = 0;
        for (String str : args) {
            array[i++] = Integer.parseInt(str);
        }

        return array;
    }

    public static long solution(long[] trees, long m) {
        Arrays.sort(trees);

        long low = 0;
        long high = trees[trees.length - 1];

        long answer = 0;

        while (low <= high) {
            long mid = (low + high) >>> 1;
            long sum = getTrees(trees, mid);

            if (sum < m) {
                high = mid - 1;
            } else {
                answer = Math.max(answer, mid);
                low = mid + 1;
            }
        }

        return answer;
    }

    private static long getTrees(long[] trees, long mid) {
        long sum = 0;
        for (int i = 0; i < trees.length; i++) {
            sum += trees[i] > mid ? trees[i] - mid : 0;
        }

        return sum;
    }
}

흐름

  1. 나무들을 크기가 큰 순서로 정렬한다.
  2. 0부터 높이가 제일 큰 나무까지 탐색하기 위해 low와 high 변수를 지정한다.
  3. low와 high의 중간 값을 구한다.
  4. 나무들을 반복하면서 중간 값 보다 크면 나무 길이와 중간 값을 뺀 값을 더한다.
  5. 그렇게 벌목한 나무를 전부 더한 값이 필요한 나무 길이인 m 보다 작으면,
  6. 벌복한 나무의 길이가 m보다 크거나 같으면, 벌목한 나무가 남는 것 이므로, 나무를 낭비하지 않기 위해 이전에 구한 중간 값(answer) 와 현재 중간 값 중 큰 값을 저장하고 중간 값 + 1 해서 최소 값을 올린다.
  7. 반대로 벌목한 나무의 길이가 m 보다 작은 경우 더 크게 자르기 위해 중간 값 - 1을 high에 저장해서 다음 루프 때 (low + high) >>> 1 에서 더 크게 잘릴 수 있도록 한다.
  8. low와 high가 같아질 때 까지 반복한다.
  9. 끝

결과

결과

테스트 케이스

1
2
3
4
5
6
7
8
9
10
11
assertEquals(15, test.solution(new long[] {20, 15, 10, 17}, 7));
assertEquals(3, test.solution(new long[] {6, 6}, 5));
assertEquals(4, test.solution(new long[] {6, 6, 6, 6}, 6));
assertEquals(500000000, test.solution(new long[] {900000000, 900000000, 900000000, 900000000, 900000000}, 2000000000));
assertEquals(19, test.solution(new long[] {20, 15, 10, 17}, 1));
assertEquals(0, test.solution(new long[] {2, 2}, 3));
assertEquals(21, test.solution(new long[] {13, 23, 21, 32}, 12));
assertEquals(2, test.solution(new long[] {1,4,5,7}, 10));
assertEquals(1, test.solution(new long[] {51, 1}, 50));
assertEquals(999999999, test.solution(new long[] {1000000000}, 1));
assertEquals(0, test.solution(new long[] {2, 2,2,2}, 8));