백준 1781번: 컵라면 (JAVA)

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

1781번: 컵라면

문제

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.

문제 번호데드라인컵라면 수

1	2	3	4	5	6	7
1	1	3	3	2	2	6
6	7	2	1	4	5	1

위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.

문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.

문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231보다 작거나 같은 자연수이다.

입력

첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

출력

첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.

 

---

 

내 시도

int[]를 데드라인에 대해 오름차순, 데드라인이 같으면 컵라면 개수에 대해 내림차순으로 정렬하는 기준으로 하는 우선순위 큐를 선언한 후, 시간을 1부터 시작하여 만약 시간보다 데드라인이 크다면 해당 일을 하며, 이후 시간을 1 늘려 데드라인이 지난 일을 빼주는 작업을 반복하였다. 예제는 원활히 되기에(이 문제는 되게 무난한 예제를 제시했더라.) 그냥 냈는데, 틀렸다.

 

틀린 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
            return (o1[0]==o2[0])? (-1) * Integer.compare(o1[1], o2[1]): Integer.compare(o1[0], o2[0]);
        });


        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            pq.offer(new int[] {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
        }

        int time = 1;
        int ans = 0;
        while (!pq.isEmpty()) {
            if (pq.peek()[0] >= time++) ans += pq.poll()[1];
            while(!pq.isEmpty() && pq.peek()[0] < time) pq.poll();
        }
        System.out.println(ans);
    }

}

반례) 

3

1 200

2 300

2 400

→ time = 1일때 200, time = 2에서 400 받는 거 보다 time = 1일때 400, time = 2일 때 300 받는 것이 좋다.

 

 

풀이

이 문제는 그리디이다: 위 풀이도 그리디이긴 한데, 잘못 생각했다.

시간 t까지 받을 수 있는 최대 라면의 개수 = 시간 t1(<t)까지 받을 수 있는 최대 라면의 개수 + 시간 t1+1부터 t까지 받을 수 있는 최대 라면의 개수가 성립하기에(왜나하면, 데드라인이 지난 과제는 뒤에 받는 라면의 개수에 영향을 끼치지 않는다.), 최적 부분 구조를 가진다.

그리고 각각의 부분 구조는 탐욕적으로 접근하여 풀면 된다.

따라서, (데드라인, 컵라면) 순서쌍을 데드라인에 대해 내림차순으로 정렬한 우선순위 큐에 넣어준다. 이후 시간 time에 따라 loop를 돌면서, time보다 데드라인이 앞서는 모든 과제에 대하여 컵라면 수를 새로 만든 최소 힙에 넣어준다. 만약 최소 힙이 time보다 크다면, time보다 많은 과제가 주어졌기에 몇몇 과제를 하지 못하게 된다. 여기서 힙의 size가 time이 될 때까지 heap에서 빼주면 된다.

 

배울 점

요즘 고민하다가 잘 안 풀리면 바로 반례 찾아보고, 그러다가 정답 찾아보곤 하는데 20분은 고민해보자. 사실 학문의 최전선에서 연구하는것이 아니라 이미 유명한 이론적인 내용을 학습하는 수준이기에 너무 많이 고민할 필요는 없지만, 또 고민을 해봐야 실제로 푸는 사고가 발전하지 않을까?

그리고 요즘들어 그리디가 진짜 어렵다고 느껴진다: 일단 감이 와야하고, 그 감이 틀릴 수도 있고, 설사 그 감이 맞아도 '이게 맞나?'하는 의문을 가지고 코드를 짜야하니...

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;
        PriorityQueue<int[]> pq1 = new PriorityQueue<>((o1, o2) -> {
            return Integer.compare(o1[0], o2[0]);
        });
        PriorityQueue<Integer> pq2 = new PriorityQueue<>();


        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            pq1.offer(new int[] {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
        }

        int time = 1;
        int ans = 0;
        while (!pq1.isEmpty()) {
            while (!pq1.isEmpty() && pq1.peek()[0] <= time) {
                pq2.offer(pq1.poll()[1]);
            }
            while (pq2.size() > time) {
                pq2.poll();
            }
            time++;
        }

        while (!pq2.isEmpty()) {
            ans += pq2.poll();
        }

        System.out.println(ans);
    }

}