[백준] 나무 자르기 2805번 - Java

[백준] 나무 자르기 2805번

나의 풀이

public class CutTree {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] values = br.readLine().split(" ");
        int N = Integer.parseInt(values[0]);
        int M = Integer.parseInt(values[1]);
        int[] trees = Arrays.stream(br.readLine().split(" ")).mapToInt(i -> Integer.parseInt(i)).toArray();
        int start = 1;
        int end = 0;
        for(int tree : trees) {
            if(end < tree) {
                end = tree;
            }
        }

        while(start <= end) {
            long m_tree = 0;
            int mid = (start + end) / 2;
            for(int tree : trees) {
                if(tree >= mid) {
                    m_tree += tree - mid;
                }
            }
            if(m_tree >= M) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        System.out.println(end);
    }
}

• 입력 값들을 받아준다.
• trees 는 스트림을 사용하여 int형 배열로 바꿔주었다.
• 최소 나무 길이가 1이기 때문에 start는 1, end 는 trees 배열 중에서 가장 큰 나무 길이를 담아준다.
• trees를 돌면서 mid 보다 크거나 같다면 빼서 m_tree 변수에 더해준다.
• 만약 m_tree 의 변수가 M보다 크거나 같다면 start = mid + 1, 아니라면 end = mid - 1 을 해준다.
• 이 과정을 start 가 end 보다 커질 때 까지 반복한다.
• 그러면 end는 조건을 만족하는 값 중에서 가장 큰 값이 된다.

느낀점

처음에 파이썬으로 풀 때와 같은 원리를 적용했는데 자꾸 실패하길래 뭐지뭐지 싶었다. m_tree 를 int로 잡아줘서 그랬던 것이였다. 나무가 많아지면 잘리고 남은 나무의 길이가 int형을 초과하기 때문이다. 때문에 long 으로 바꿔줘야 한다.