[백준 / 골드2] 1781 컵라면 (Java)

문제 보기

사용한 것

• 최대 컵라면 수를 구하기 위한 그리디
• 과제를 컵라면 수로 오름차순 하기 위한 우선순위 큐

풀이 방법

• Homework를 deadline, num(컵라면 수) 필드로 만든다.
• 숙제를 모두 입력 받고(homeworks) deadline으로 오름차순 한다.
• 컵라면 오름차순으로 우선순위 큐 pq를 초기화한다.
• homeworks를 순회하며
  • pq에 넣고
  • pq의 크기가 deadline보다 크면 같아질 때까지 컵라면 개수가 가장 낮은 것을 뺀다.

하루에 한 문제만 풀 수 있으므로 pq의 크기는 지난 날짜와 같다.
현재 pq에 추가한 숙제의 deadline이 pq의 크기보다 작다면 같아질 때까지 pq에 있는 숙제들을 버려야 한다.
버릴 때는 가장 컵라면 수가 적은 숙제를 버려야 하므로, num으로 오름차순한 pq를 사용한 것이다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        List<Homework> homeworks = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int deadline = Integer.parseInt(st.nextToken());
            int num = Integer.parseInt(st.nextToken());
            homeworks.add(new Homework(deadline, num));
        }

        // 그리디
        Collections.sort(homeworks, comparingInt(o -> o.deadline));
        PriorityQueue<Homework> pq = new PriorityQueue<>(comparingInt(o -> o.num));
        for (Homework homework : homeworks) {
            pq.offer(homework);
            while (pq.size() > homework.deadline) {
                pq.poll();
            }
        }

        int answer = 0;
        while (!pq.isEmpty()) {
            answer += pq.poll().num;
        }

        System.out.println(answer);
    }
}

class Homework {

    public int deadline;
    public int num;

    public Homework(int deadline, int num) {
        this.deadline = deadline;
        this.num = num;
    }
}