[BOJ] 백준 13904 : 과제 (java)

🧪 13904 과제

---

난이도 : 🌟 골드 3
유형 : 그리디 알고리즘

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

 

📝 문제

---

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

 

입력

 

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

 

출력

 

얻을 수 있는 점수의 최댓값을 출력한다.

 

🧐 핵심 로직 

---

1) 마감기한이 가장 긴 날짜부터 거꾸로 탐색한다면 매 선택마다 최적의 해를 고를 수 있다.

 

2) 날짜와 점수를 저장하는 Scroe 클래스를 만들고 Score 타입을 리스트를 통해 저장한다.

 

3) 마감기한이 가장 긴 날짜부터 차레로 탐색을 시작하고 가능한 큰 점수를 계속해서 res에 더해준다.

    3 - a) 이때, 모든 탐색이 완료된 후 list에서 사용했던 점수와 날짜는 제거해준다.

 

💻 최종 코드 (184 ms)

---

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

public class Main {

    static class Score {

        int d, w;

        Score(int d, int w) {
            this.d = d;
            this.w = w;
        }
    }

    static int n, d, w, maxDay, res;
    static List<Score> scores;
    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        n = Integer.parseInt(br.readLine());
        maxDay = Integer.MIN_VALUE;

        scores = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            d = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());

            scores.add(new Score(d, w));
            maxDay = Math.max(maxDay, d);
        }

        maxScore();

        System.out.println(res);

        br.close();
    }

    private static void maxScore() {

        for (int i = maxDay; i >= 1; i--) {
            Score ans = new Score(0, 0);

            for (Score score : scores) {
                if (score.d >= i) {
                    if (ans.w < score.w) {
                        ans = score;
                    }
                }
            }

            res += ans.w;
            scores.remove(ans);
        }
    }
}