컵라면 - 백준 BOJ 1781

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

1781번: 컵라면

 

 

 

---

접근

인터벌 스케줄링이 생각나는 문제이다.

각 숙제별로 마감기한이 존재하고, 해당 숙제를 했을 때 얻을 수 있는 컵라면의 수가 주어질 때, 얻을 수 있는 컵라면의 최댓값을 구하는 문제이다.

 

우선 데드라인의 오름차순으로 숙제들을 정렬하고, 동일한 데드라인에 대해서는 컵라면의 개수의 내림차순으로 정렬을 수행했다.

숙제 하나를 푸는데 단위시간 1이 소요되므로, 현재 날짜를 나타내는 변수를 1 부터 증가하면서, 현재 날짜의 데드라인에 속해있는 숙제들 중 컵라면이 큰 숙제부터 푸려고 했으나...

 

3
1 1
2 100
2 100

// 최대는 200, 하지만 101 이 나올 수 있다

 

위의 예시같이 데드라인이 1 인 숙제를 첫날에 수행하지 않아도 최적이 되는 해가 존재하는 경우가 있다.

 

얻을 수 있는 컵라면 수의 최대는 각 날짜에서 얻을 수 있는 컵라면 개수가 최대이므로, 메모이제이션을 통해, 특정 날짜에서 선택할 수 있는 최선의 컵라면 수를 업데이트 해가며 문제를 해결해 가려고 했다.

 

데드라인이 4인 숙제들이 2개가 있다고 해보자. 그럼 이 숙제들을 통해 메모이제이션을 최대로 업데이트 하려면 3 일부터 해당 날짜에 얻을 수 있는 컵라면을 최대로 업데이트 할 수 있는지 확인하게 될 것 이다.

 

이러한 다이내믹 프로그래밍을 통한 풀이는 한가지 조건이 존재하는데,

상위의 문제가 하위의 문제를 포함하여야 한다

는게 그 조건이다

 

정말 위 풀이가 최적의 해를 도출할까?  간단한 예시를 하나 보자

 

5
1 1
3 4
5 6
5 6
5 6

// 1 0 6 6 6 
// 이 DP 의 최종 상태가 된다
// 
// 하지만 최적은
// 1 4 6 6 6

 

 

DP 를 통한 풀이는 위의 예시와 같이 최적의 해를 구하지 못한다.

이는 매 날짜에 얻을 수 있는 컵라면의 최대 개수를 업데이트 하며 발생하는 문제인데,

이를 해결하려면 데드라인이 n 인 숙제들이 k 개 있다고 할 때,

시작날짜를 n-k+1 일 부터 n 일까지 전부 살펴봐야지 최적의 해가 도출된다

이 때 시간복잡도는 최악의 경우 O(N^2) 이며 시간초과가 발생 ( 애초에 N^2 이 되면 DP 를 통한 최적화를 못 이룬것이다 )

따라서 DP 는 이 문제에서의 해답이 되지 않을것이라 판단했다.

 

---

풀이

30분동안 고민해도 답이 나오지 않아 다른 사람의 풀이를 참고했다.

 

총 얻을 수 있는 컵라면 수의 최대 -> 각 날짜에서 얻을 수 있는 컵라면 개수가 최대

위 조건을 살짝 바꿔서 생각해보면, N 일차에 선택할 숙제들은 현재까지 선택했던 숙제들에서, 현재 추가적으로 고를 수 있는 숙제들 중 컵라면을 보다 많이 얻을 수 있는 숙제가 있다면 이를 교체하면 되는 것이다.

해당 작업은 우선순위 큐를 활용해 효율적으로 진행할 수 있으므로,

N 일차까지 들고있는 숙제들의 리스트를 컵라면의 오름차순으로 정렬된 우선순위 큐에 담아놓고,

데드라인이 N 일인 모든 컵라면을 우선순위에 추가.

우선순위 큐의 크기가 N 이 될 때 까지 숙제들을 우선순위 큐에서 제거하면 된다.

 

 

한가지 더 주의해야할게...

 

 

2^31 보다 작으니까 int 겠지~~ 하고 나처럼 틀렸던 사람이 없길 바란다..ㅠ

int 의 범위는 [-2^31, 2^31 - 1] 이다ㅠㅠ

 

즉 정답은 long (자바기준) 으로 출력해야한다

 

---

코드

 

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        Map<Integer, PriorityQueue<Long>> ramenByDeadline = new HashMap<>();

        for(int i = 0; i < n; i++) {
            int[] inputs = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int deadLine = inputs[0];
            long ramen = inputs[1];

            PriorityQueue<Long> pq = ramenByDeadline.getOrDefault(deadLine, new PriorityQueue<>(Comparator.reverseOrder()));
            pq.add(ramen);

            ramenByDeadline.put(deadLine, pq);
        }

        PriorityQueue<Long> ramenPQ = new PriorityQueue<>();

        for(int day = 1; day <= 200001; day++) {
            if(!ramenByDeadline.containsKey(day)) {
                continue;
            }

            PriorityQueue<Long> pq = ramenByDeadline.get(day);
            ramenPQ.addAll(pq);

            while(ramenPQ.size() > day) {
                ramenPQ.poll();
            }
        }

        System.out.println(
                ramenPQ.stream().reduce(0L, Long::sum)
        );
    }
}