백준 1781 컵라면(java)

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

1781번: 컵라면

처음엔 부분합을 최대로 하는 문제라고 생각했지만 lowebound를 구하는 과정에서 그게 아니라는 걸 알게됐다.

 

데드라인 기준으로 오름차순 정렬을 한다.

차례대로 우선순위 큐에 라면을 넣으면서, 개수가 데드라인을 넘어가면 제일 라면이 적은 것부터 빼낸다.

 

데드라인은 배열의 크기로 볼 수 있다. 만약 어떤 한 과제의 데드라인이 3이라면 배열에서 0~2까지 인덱스에 들어갈 수 있다.

 

꼭 2에 들어갈 필요가 없다는 뜻이다.

 

그렇기 때문에 우선순위 큐를 이용해서, 라면값을 기준으로 정렬할 필요가 있다. 

 

import java.io.*;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Race implements Comparable<Race> {
    int pNum, deadline, ramenNum;

    Race(int a, int b, int c) {
        pNum = a;
        deadline = b;
        ramenNum = c;
    }

    @Override
    public int compareTo(Race o) {
        return Integer.compare(this.deadline, o.deadline);
    }
}

public class boj1781 {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer st;
    static int N;
    static Race[] problems;

    public static void main(String[] args) throws Exception{
        input();
        solve();
        bw.flush();
    }

    static int pI(String s) { return Integer.parseInt(s);}

    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = pI(st.nextToken());
        problems = new Race[N];

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            problems[i] = new Race(i+1, pI(st.nextToken()), pI(st.nextToken()));
        }
    }

    static void solve() throws IOException {
        // 데드라인 기준으로 정렬한다.
        Arrays.sort(problems);

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

        for(int i = 0; i < N;i++){
        // 현재 데드라인보다 많은 수의 과제를 수행할 수 없다.

            // 작은 것부터 위로오게 한다.
            pq.add(problems[i].ramenNum);
            while(pq.size() > problems[i].deadline)
                pq.poll();
        }

        int ans = 0;
        while(!pq.isEmpty())
            ans += pq.poll();

        bw.write(""+ans);
    }
}