백준 13904 과제 (Java)

목차

• 문제명
• 문제풀이
• 코드

 

백준 13904 과제

 

문제 유형 : 그리디 (Greedy )

난이도 : 골드 3

 

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

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

/*
날짜 기준으로 정리하면
6 : 5
5 : X
4 : 60, 40, 10
3 : 30
2 : 50
1 : 20
*/

 

마지막 날짜는 6일이므로 6일차부터 탐색하면

 

6일차에 선택할 수 있는 과제는 5점 과제뿐입니다.

 

5일차에 선택할 수 있는 과제는 없습니다.

 

4일차에 선택할 수 있는 과제는 60, 40, 10점 과제입니다. 이 중 점수가 가장 큰 60점 과제를 선택합니다.

 

3일차에 선택할 수 있는 과제는 40, 10, 30점 과제입니다. 이 중 점수가 가장 큰 40점 과제를 선택합니다.

 

2일차에 선택할 수 있는 과제는 10, 30, 50점 과제입니다. 이 중 점수가 가장 큰 50점 과제를 선택합니다.

 

1일차에 선택할 수 있는 과제는 10, 30, 20점 과제입니다. 이 중 점수가 가장 큰 30점 과제를 선택합니다.

 

그리하여 최대 점수로 5 + 60 + 40 + 50 + 30 = 185점을 얻을 수 있게 됩니다.

 

 

 

코드

 

과제들을 배열에 담아 점수를 기준으로 내림차순 정렬합니다.

 

가장 큰 day부터 거꾸로 탐색하면서 day보다 큰 d값을 가진 첫 번째 과제를 찾으면 과제의 w값을 저장하고 배열에서 해당 과제를 제거합니다. 이 과정을 day가 0에 다다를 때까지 반복합니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

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

        ArrayList<HW> list = new ArrayList<>();

        int maxD = -1;

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

        Collections.sort(list, new Comparator<HW>() {
            @Override
            public int compare(HW o1, HW o2) {
                return Integer.compare(o1.w, o2.w) * -1;
            }
        });

        int sum = 0;
        int day = maxD;

        while (day > 0) {
            for (int i = 0 ; i < list.size() ; i++) {
                HW hw = list.get(i);
                if (day <= hw.d) {
                    sum += hw.w;
                    list.remove(i);
                    break;
                }
            }
            day--;
        }

        System.out.println(sum);
    }
}

 

 

 

마무리