boj13904: 과제

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

 

접근 방법

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());

        PriorityQueue<int []> pq = new PriorityQueue<>((a,b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1]; // 날짜가 같다면 큰 값
            };
            return b[0] - a[0]; // 날짜 큰 순서대로
        });
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            pq.add(new int [] {d,w});
        }

        int total = 0;
        while(!pq.isEmpty()) {
            int [] cur = pq.poll();
            int day = cur[0];
            int score = cur[1];

            total += score;

            List<Integer> tmp = new ArrayList<>();
            while (true) {
                if (pq.isEmpty() || pq.peek()[0] != day) break;
                int [] nxt = pq.poll();
                tmp.add(nxt[1]);
            }

            if (!pq.isEmpty()) for(Integer next : tmp) pq.add(new int[]{pq.peek()[0], next});
        }

        System.out.println(total);
    }
}

 

먼저 가장 늦은 날짜부터 돌면서, 해당 날짜의 최대값을 더해줬다. 만약에 해당 날짜에 얻을 수 있는 점수가 더 있다면, 다음 날짜로 이월시켜서 더해주는 방식으로 문제를 풀이했다.

 

이렇게 해서 테스트 케이스는 맞았지만, 하루에 하나씩 처리한다는 조건에 위배되어 틀렸다.

 

올바른 풀이

1. 입력값을 리스트 형태에 저장하고, 리스트를 날짜 기준 내림차순 순서대로 정렬한다.
2. 우선순위 큐를 선언하고, 내림차순으로 정렬해준다.
3. for문을 돌 때, 마감일이 제일 느린 날짜부터 순회한다.
   1. 이 때, 아직 처리하지 않은 과제들 중에 day일 이상인 과제를 모두 우선순위 큐에 넣어준다.
4. 큐가 비어있지 않다면, 결과값에 큐를 뺀 값을 더해준다.

이렇게 했을 때

 

6: [5]

4: [60, 40, 10]

3: [30]

2: [50]

1: [20]

 

6일차: 5 -> 4일차: 60 -> 3일차: 40 -> 2일차: 50 -> 1일차: 30

 

이렇게 계산이 되며, 결과값인 185를 얻을 수 있다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class boj13904 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

       List<int[]> list = new ArrayList<>();

       int maxDay = 0;
        for(int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list.add(new int[]{d, w});
            maxDay = Math.max(maxDay, d);
        }

        list.sort((a,b) -> b[0] - a[0]); // 마감일 높은 순서대로 정렬

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        int total = 0;
        int idx = 0;

        for(int i = maxDay; i >= 1; i--) {
            while(idx < n && list.get(idx)[0] >= i) {
                pq.add(list.get(idx)[1]);
                idx++;
            }

            if (!pq.isEmpty()) {
                total += pq.poll();
            }
        }
        System.out.println(total);
    }
}