백준 13904번 - 과제 [JAVA]

🧩 문제

---

▶ 백준 13904 과제 바로가기

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

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

입력

---

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

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

출력

---

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

예제

---

입력

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

출력

185

🎯 풀이

---

메모리	시간	코드길이
12720 KB	140 ms	1460 B

Point

1. 마감일과 현재 날짜의 원활한 비교를 위해 입력받으면서 최대 날짜도 구한 후, 뒤에서 부터 비교한다.
2. list를 사용하며, 해결한 과제는 list에서 없애준다.

for(int day = maxDay; day >= 1; day--) {

    Assignment haveToDo = new Assignment(0, 0);

    for(Assignment a:assignments) {
        if(a.d >= day && a.w > haveToDo.w) haveToDo = a;
    }

    sum += haveToDo.w;
    assignments.remove(haveToDo);

}

입력받으면서 구한 과제를 수행하는 기간(maxDay)에서부터 첫째 날까지 뒤에서부터 비교하며 구한다. list를 탐색하며 마감일자가 현재 날짜보다 작으며 과제 점수는 가장 큰 것을 haveToDo에 업데이트 시킨다. 과제를 선택했다면 해당 과제의 점수를 sum에 더하고 list에서 삭제시킨다.

⭐️ 전체 풀이 코드

---

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

public class BJ13904_과제 {

    private static class Assignment {
        int d, w;

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

    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        List<Assignment> assignments = new ArrayList<Assignment>() {
        };
        int sum = 0;
        int maxDay = 0;

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

        for(int day = maxDay; day >= 1; day--) {

            Assignment haveToDo = new Assignment(0, 0);

            for(Assignment a:assignments) {
                if(a.d >= day && a.w > haveToDo.w) haveToDo = a;
            }

            sum += haveToDo.w;
            assignments.remove(haveToDo);

        }

        System.out.println(sum);

    }   //main 끝

}