[ Baekjoon - 11/08 ] - 1781번: 컵라면

• 문제 링크 : https://www.acmicpc.net/problem/1781

1781번: 컵라면

 

• 소요 시간 : 2시간 반

컵라면 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

9247

2741

2059

31.122%

문제

상욱 조교는 동호에게 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번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.

출력

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

예제 입력 1 복사

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

예제 출력 1 복사

15

 

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 256MB
   • 문제
     
     • N개의 숙제(1 ≤ N ≤ 200,000), 1 ≤ 각 문제를 풀때 받는 컵라면과 최대로 받을 수 있는 컵라면 수 ≤ 2^31
     • 각 문제마다 문제번호, 마감시간, 컵라면의 수가 각각 주어진다.
     • 문제를 풀면 컵라면을 얻을 수 있지만, 풀기위해서는 각 문제의 데드라인 내에 풀어야한다.
     • 이때, 최대로 얻을 수 있는 컵라면의 개수를 출력하는 문제 
   • 이해
     • 문제가 굉장히 단순해 보였고, 그리디를 써야할것같다고 생각했다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 입출력 형식에 맞게, 각 변수의 조건과 시공간 조건을 적어보았고, 입출력 예제를 다시 그려보았다.
   • 그리디를 써야할 것 같았는데, 생각보다 예제가 단순해보여서 잘만하면 정렬로 끝낼 수 있을거라 생각하고 첫번째 접근을 시도했다.. 
3. 문제를 어떻게 해결할 것인가
   • 1st 접근 - 가짜 그리디, 정렬만..)

     • 

     • 가짜 그리디라 한 이유는 2번째 접근까지 하고나서야 이 그리디적 접근은 틀렸다고 생각했기 때문...
     • 우선 모든 숙제를 푸는 시간은 전부 1의 시간(부럽..)이기때문에, 순서가 가장 핵심이라 생각했다.
     • 우선 시간이 겹치는 경우는 데드라인이 같을때 뿐이므로, 데드라인으로 정렬해야했고
       컵라면의 개수를 큰것을 선택해야하므로
       마감시간은 오름차순, 컵라면의 수는 내림차순으로 정렬해야한다 생각했다.
     • 그리고 해당 입출력 예제의 경우, 정렬만해도 딱 떨어지도록 답이 도출되어서... 정렬만으로 가능했다.
       ( 하지만 이는 반례를 보고 불가하다는것을 깨달았지만.. ) 
     • 사실 구현방식을 해쉬맵(딕셔너리)로 할지 리스트를 행렬처럼 연결할지 좀 고민했는데 손이 좀 더 익숙한 리스트로 구현해보았다.
     •  틀렸습니다를 얻었는데 너무 이해가 가질 않아서 질문하기에서 반례를 찾으러 들어갔다.
       그런데 반례 두개가 확실하게 내 코드가 이상함을 증명하는 아이들이었다.. 다들 나같은 접근을 했구나..
       ( 각 반례는 사진의 왼쪽 하단의 두개이다. )
     • 하나는 같은 마감기한이라면 꼭 하나만을 고르지 않아도 가능한 경우가 있음을 증명하는 케이스였고,
       나머지 하나는 가능한 마감기한이 있어도, 긴 마감이지만 더 좋은 컵라면의 개수를 가진다면 해당 아이를 채택해야함을 보여주는 케이스였다.
     • 위 반례들을 보며 내 코드가 잘못된 이유를 알아내어 첫번째 케이스는 보완이 간단했지만, 두번째 케이스는 도저히 현 코드로서는 수정이 불가해보였다..ㅠ
     • 그렇게 두번째, 진짜 그리디를 쓰게 되었다.
   • 2nd 접근 - 진짜 그리디, 정렬과 큐를 사용)

     • 

     • 그리디스러운 그리디접근법을 하기위해, 우선 정렬을 해야했는데 정렬은 그대로 가는게 맞아보였고 이제 그 뒤 처리를 어떤식으로 각색하느냐가 문제였다.
     • 시나리오를 생각해보았는데,
       위 2번째 반례의 경우, 긴 마감이어도 더 좋은 컵라면의 수를 가진다면 채택해야함 이였기 때문에
       그러면 어떻게 현재 숙제들 중 최적의 숙제들만 보관할 수 있을지 고민해보았다..
     • 아무리 생각해도... 한번에 최적의 숙제들을 정렬만을 통해서는 구하기가 어려워보여서, 가장 Worst, 즉 가장 안타까운 개수의 컵라면을 받는 숙제를 먼저 꺼내서 버릴수만 있으면 될 것이라 생각했다.
       결국 가장 안타까운 개수도 정렬을 통해 얻을 수 있지만, 이미 리스트는 정렬을 했기 때문에 또 정렬은 무의미하므로 현재까지의 결과값만 따로 저장할 공간이 필요하다 생각했고 이를 위해 우선순위 큐를 채택했다!
     • 현재까지 실행된 묶음(pq가 보관)에서 현재 실행시간 이내에 가능한 아이가 나타나면, pq에서는 가장 컵라면의 개수가 안타까운 아이와 비교해서 pq아이가 더 작다면 얘를 버리고 가능한 아이를 넣는 식으로 짜면 될것이라 생각했다!
4. 위 계획을 검증
   • 컵라면의 최대개수를 출력하는 문제이므로, 이때까지 보관한 컵라면의 개수들을 비교하며 순간순간의 최대값들만 취하는 형태이므로 가능하다.
   • 게다가 이때까지 보관한 모든 숙제들과 새롭게 등장한 숙제를 비교하는 것이 아닌, 가장 안타까운 컵라면의 개수를 가진 숙제와 비교하는 것이기 때문에 좀더 안정적으로 수행될 수 있을거라 생각한다.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.io.*;
        import java.util.*;
        
        public class Main {
            static int N;
            static long nowCupNoodleCount = 0;
            static Homework[] hArr;
            static PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        
            public static void main(String args[]) throws NumberFormatException, IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
                N = Integer.parseInt(br.readLine());
                hArr = new Homework[N];
        
                for(int n = 0; n < N; n++) {
                    StringTokenizer st = new StringTokenizer(br.readLine());
                    hArr[n] = new Homework(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
                }
        
                Arrays.sort(hArr);
        
                for(Homework Homework : hArr) {
                    // 모든실행은 1단위이므로, pq사이즈는 현재 실행 시간임
                    if(pq.size() < Homework.deadLine) {
                        pq.offer(Homework.noodlesNum);
                    }
                    // 해당 마감기한이 현재 실행시간과 같다면
                    else if(pq.size() == Homework.deadLine) {
                        // 담아둔 숙제 중 작은 컵라면의 수를 현재 컵라면개수와 비교했을때, 현재 들어온 컵라면이 더 많다면
                        if(pq.peek() < Homework.noodlesNum) {
                            // 삭제하고
                            pq.poll();
                            // 넣기
                            pq.offer(Homework.noodlesNum);
                        }
                    }
                }
        
                // 실행한 숙제의 컵라면 수 합산
                while(!pq.isEmpty()) {
                    nowCupNoodleCount += pq.poll();
                }
        
                bw.write(nowCupNoodleCount+"\n");
                bw.flush();
            }
        }
        
        class Homework implements Comparable<Homework> {
            int deadLine;
            int noodlesNum;
        
            Homework(int deadLine, int noodlesNum) {
                this.deadLine = deadLine;
                this.noodlesNum = noodlesNum;
            }
        
            @Override
            public int compareTo(Homework o) {
                // 마감기한 오름차순, 컵라면 내림차순
                if(deadLine == o.deadLine) {
                    return o.noodlesNum - noodlesNum;
                }
                return deadLine - o.deadLine;
            }
        
            @Override
            public String toString() {
                return "Homework{" +
                        "deadLine=" + deadLine +
                        ", noodlesNum=" + noodlesNum +
                        '}';
            }
        }

   2. Python 3

      • import sys
        import heapq
        
        input = sys.stdin.readline
        
        def solution():
            N = int(input())
            hArr = [list(map(int, input().split())) for _ in range(N)]
            
            # 마감기한 오름차순, 컵라면 수 내림차순
            hArr = sorted(hArr, key=lambda x: (x[0], -x[1]))
        
            pq = []
            for h in range(len(hArr)):
                #  모든실행은 1단위이므로, pq사이즈는 현재 실행 시간임
                if len(pq) < hArr[h][0]:
                    heapq.heappush(pq, hArr[h][1])
                # 해당 마감기한이 현재 실행시간과 같다면
                elif len(pq) == hArr[h][0]:
                    # 담아둔 숙제 중 작은 컵라면의 수를 현재 컵라면개수와 비교했을때, 현재 들어온 컵라면이 더 많다면
                    if pq[0] < hArr[h][1]:
                        # 삭제하고 넣기
                        heapq.heappop(pq)
                        heapq.heappush(pq, hArr[h][1])
        
            # 실행한 숙제의 컵라면 수 합산
            ans = 0
            while pq:
                ans += pq.pop()
            print(ans)
        
        
        if __name__ == '__main__':
            solution()

6. 회고하기
   • "그리디를 풀기 위해선 정렬을 하고 들어가야한다" 정도만 터득하고있어서 그리디임을 알아도 바로 그리디를 구현해내지는 못하는 것 같다ㅜ 해당 문제의 특징을 파악하여 적절한 알고리즘을 채택하는 연습을 좀 더 해야할듯 싶다. 이참에 다시 이론책을 펴봐야할것같기도하고.

 

• 결과