[백준] 1781번 컵라면

문제 설명

• https://www.acmicpc.net/problem/1781
• Gold 2
• 소요 시간 : 25분

문제 풀이

• 우선 입력을 배열로 만들고 데드라인 오름차순, 보상개수 내림차순으로 정렬한다.
• 배열 앞에서 부터 컵라면 개수를 대상으로하는 우선순위 큐에 보상개수를 넣어주되 큐 사이즈가 데드라인을 넘어서게 되면 poll을 해준다. (PQ가 해당 데드라인까지 가능한 모든 보상에 대한 고려를해서 작은 것들만 빼준다고 보면됨)

소스 코드 (JAVA)

import java.io.*;
import java.util.*;

public class Main {

    static class Point implements Comparable<Point>{
        int d, c;

        public Point(int d, int c) {
            this.d = d;
            this.c = c;
        }

        @Override
        public int compareTo(Point o) {
            if (this.d > o.d) return 1;
            else if (this.d < o.d) return -1;
            else {
                if (this.c < o.c) return 1;
                else if (this.c > o.c) return -1;
                else return 0;
            }
        }
    }
    static int N;
    static Point[] arr;
    static void solve() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        arr = new Point[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(arr);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            pq.add(arr[i].c);
            if (arr[i].d < pq.size()) pq.poll();
        }

        int result = 0;
        while(!pq.isEmpty()) result += pq.poll();
        bw.write(result + "\n");
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        solve();
    }
}

/**
 * 컵라면 (17:04)
 *
 * - N : 문제 번호 ( N <= 20만 )
 * - 데드라인 ( e <= N)
 * - 보상개수 ( c <= 2^31)
 * - 받을 수 있는 최대 컵라면 개수 출력
 *
 * - 그리디
 * - 데드라인 오름차순, 보상개수 내림차순 정렬
 * - 앞에서부터 PQ에 넣고 사이즈가 현재 데드라인 넘어서면 PQ에서 뺴줌
 *
 * 1 1 2 2 3 3 6
 * 7 6 5 4 2 1 1
 *
 * N
 * d c
 * ...
 */