[백준] 16206번 : 롤케이크 java

문제 설명

오늘은 재현이의 생일이다. 재현이는 친구 N명에게 롤케이크를 1개씩 선물로 받았다. 롤케이크의 길이는 A1, A2, ..., AN이다. 재현이는 길이가 10인 롤케이크만 먹는다. 따라서, 롤케이크를 잘라서 길이가 10인 롤케이크를 최대한 많이 만들려고 한다.

롤케이크는 다음과 같은 과정을 통해서 자를 수 있다.

1. 자를 롤케이크를 하나 고른다. 길이가 1보다 큰 롤케이크만 자를 수 있다. 이때, 고른 롤케이크의 길이를 x라고 한다.
2. 0보다 크고, x보다 작은 자연수 y를 고른다.
3. 롤케이크를 잘라 길이가 y, x-y인 롤케이크 두 개로 만든다.

재현이는 롤케이크를 최대 M번 자를 수 있다. 이때, 만들 수 있는 길이가 10인 롤케이크 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 롤케이크의 개수 N과 자를 수 있는 최대 횟수 M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄에 롤케이크의 길이 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 1,000)

출력

재현이가 만들 수 있는 길이가 10인 롤케이크 개수의 최댓값을 출력한다.

 

예제

 

풀이

먼저 우선순위 큐에 값을 넣어주는데 정렬 기준은 다음과 같다.
1.  n % 10 ==  0 이고,
2. 나눠지는 애들중에서도 값이 작은애들은 앞에 넣어준다.

이유는 만약 값이 30, 40, 20 있을 때
20을 먼저 처리해줘야 한번의 커팅으로 
10짜리 길이의 케잌이 2개 생기기 때문이다.

 

public class Bj16206 {
    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());
        int M = Integer.parseInt(st.nextToken());
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator
                .comparingInt((Integer num) -> num % 10)
                .thenComparingInt(num -> num));


        int count = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            if (num == 10) {
                count++;
                continue;
            }
            if (num < 10) continue;  // 작은 애들은 넣어줄 필요도 없음

            pq.add(num);
        }

        while (M > 0 && !pq.isEmpty()) {
            Integer poll = pq.poll();

            if (poll - 10 == 10) {  // 혹시 값이 20이면 10 짜리 케잌이 2개 생긴다.
                count++;
            }

            if (poll - 10 > 10) {
                pq.add(poll - 10);
            }

            count++;
            M--;
        }

        System.out.println(count);
    }
}