[백준 / Java] 13904: 과제 (그리디)

난이도: Gold 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 복사

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

예제 출력 1 복사

185

힌트

예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.

---

 

문제에 주어진 데이터들을 저장할 정적 멤버 클래스를 다음과 같이 선언하자.

 

 

    static class Homework {

        int d;  // 과제 마감일까지 남은 일수

        int w;  // 과제의 점수

       

        Homework(int d, int w) {

            this.d = d;

            this.w = w;

        }

    }

 

 

그리고 과제 개수를 입력받을 N, 위에서 선언한 Homework 타입 과제들을 저장할 ArrayList인 homeworks, 과제 마감일까지 남은 일수(d)의 최댓값 maxDay를 다음과 같이 선언하자.

 

 

    int N = Integer.parseInt(br.readLine());        // 과제 개수

    List<Homework> homeworks = new ArrayList<>();   // 과제들을 담은 리스트

    int maxDay = 0;     // 과제 마감일까지 남은 일수의 최댓값

 

 

N개의 과제들을 homeworks 리스트에 추가하고, maxDay의 값을 갱신한다.

 

 

    for (int i = 1; i <= N; i++) {

        StringTokenizer st = new StringTokenizer(br.readLine());

        int d = Integer.parseInt(st.nextToken());   // 과제 마감일까지 남은 일수

        int w = Integer.parseInt(st.nextToken());   // 과제의 점수

       

        homeworks.add(new Homework(d, w));  // 과제 리스트에 추가

        maxDay = Math.max(maxDay, d);       // 남은 일 수의 최댓값 갱신

    }

 

 

우리가 출력할 변수 result에 차례대로 누적시킬 것이다.

 

 

   int result = 0;     // 얻을 수 있는 점수의 최댓값

 

 

핵심 풀이 코드를 보기 전에 그림으로 먼저 로직 설명을 하겠다.

 

정렬을 하지 않고 받은 데이터의 순서 그대로 리스트에 저장되어 있는 상태이다.

문제에 주어진 데이터를 기준으로, maxDay는 6이 된다.

maxDay(6)부터 1까지 역순으로 탐색하면서 해당 일차에 해당하는 과제들 중 가장 큰 값을 선택할 것이다.

 

 

6일차에 수행할 수 있는 과제의 일 수는 6 이상이다.

여기서는 1개밖에 해당하지 않으므로 5점짜리 과제를 선택해서 최종 출력할 변수 result에 더한다.

 

 

위에서 수행한 과제는 리스트에서 지운다.

5일차에 수행할 수 있는 과제의 일 수는 5 이상이다.

여기서는 해당하는 과제가 없으므로 넘어간다.

 

 

4일차에 수행할 수 있는 과제의 일 수는 4 이상이다.

여기서는 3개가 해당하는데, 60점이 가장 크므로 60점짜리 과제를 선택해서 최종 출력할 변수 result에 더한다.

 

위에서 수행한 과제는 리스트에서 지운다.

3일차에 수행할 수 있는 과제의 일 수는 3 이상이다.

여기서는 3개가 해당하는데, 40점이 가장 크므로 40점짜리 과제를 선택해서 최종 출력할 변수 result에 더한다.

 

 

위에서 수행한 과제는 리스트에서 지운다.

2일차에 수행할 수 있는 과제의 일 수는 2 이상이다.

여기서는 3개가 해당하는데, 50점이 가장 크므로 50점짜리 과제를 선택해서 최종 출력할 변수 result에 더한다.

 

 

위에서 수행한 과제는 리스트에서 지운다.

1일차에 수행할 수 있는 과제의 일 수는 1 이상이다.

여기서는 3개가 해당하는데, 30점이 가장 크므로 30점짜리 과제를 선택해서 최종 출력할 변수 result에 더한다.

 

 

1일차까지 모두 과제를 선택했으므로, 최종 result의 값은 위 값들을 모두 더한 185가 된다. 

이제 이 로직을 코드로 보자.

 

    int result = 0;     // 얻을 수 있는 점수의 최댓값

    // 과제 마감일까지 남은 일 수의 최댓값부터 1까지 역순으로 탐색

    for (int i = maxDay; i >= 1; i--) {     // i일차

        int max = 0;        // i일차에 얻을 수 있는 과제 점수의 최댓값

        int index = -1;     // max에 해당하는 과제의 인덱스

       

        // 과제 리스트의 크기만큼 탐색

        for (int j = 0; j < homeworks.size(); j++) {

            Homework homework = homeworks.get(j);   // j번째 과제

           

            // i일차가 해당 과제의 남은 일수 d 이하이고,

            // i일차에 얻을 수 있는 과제 점수의 최댓값 max보다 해당 과제 점수 w가 더 크다면

            if (i <= homework.d && homework.w > max) {

                max = homework.w;   // 과제 점수 최댓값 갱신

                index = j;          // max에 해당하는 과제의 인덱스 갱신

            }

        }

       

        // max에 해당하는 과제의 인덱스가 -1이 아니라면

        // i일차에 얻을 수 있는 과제 점수의 최댓값을 찾은 것임

        if (index != -1) {

            // 얻을 수 있는 점수의 최댓값에 i일차에 얻을 수 있는 점수의 최댓값을 더하기

            result += max;

            // max에 해당하는 과제를 수행했으므로 과제 리스트에서 인덱스 제거

            homeworks.remove(index);

        }  

    }

   

    System.out.println(result);     // 얻을 수 있는 점수의 최댓값 출력

 

 

 

자료구조로 분류되어있길래 우선순위 큐로 문제 풀이를 시도해봤는데 너무 안 풀렸다.

그래서 알고리즘 전체 분류를 보니 그리디라고 되어있었다....

그리디는 내가 제일 못하는 알고리즘이다. 이건 나한테 있어서 그냥 구현이다... 구현을 못하니 그냥 답이 없다...

알고리즘을 7개월째 거의 매일 풀고 있는데 실력이 참 신기할 정도로 늘지 않는다.

그나마 BFS나 백트래킹만 1시간 내로 풀 수 있을 정도이다. 그러나 이것도 헤매면 몇시간째 붙잡게 된다.

나머지는... 진짜 답이 없다.. 알고리즘은 재능의 영역인 걸까...? 일단은 자신없는 유형 위주로 더 풀어봐야겠다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class P13904_과제 {
    static class Homework {
        int d;    // 과제 마감일까지 남은 일수
        int w;    // 과제의 점수
        
        Homework(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));
        int N = Integer.parseInt(br.readLine());        // 과제 개수
        List<Homework> homeworks = new ArrayList<>();    // 과제들을 담은 리스트
        int maxDay = 0;        // 과제 마감일까지 남은 일수의 최댓값
        
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int d = Integer.parseInt(st.nextToken());    // 과제 마감일까지 남은 일수
            int w = Integer.parseInt(st.nextToken());    // 과제의 점수
            
            homeworks.add(new Homework(d, w));    // 과제 리스트에 추가
            maxDay = Math.max(maxDay, d);        // 남은 일 수의 최댓값 갱신
        }
        
        int result = 0;        // 얻을 수 있는 점수의 최댓값
 
        // 과제 마감일까지 남은 일 수의 최댓값부터 1까지 역순으로 탐색
        for (int i = maxDay; i >= 1; i--) {        // i일차
            int max = 0;        // i일차에 얻을 수 있는 과제 점수의 최댓값
            int index = -1;        // max에 해당하는 과제의 인덱스
            
            // 과제 리스트의 크기만큼 탐색
            for (int j = 0; j < homeworks.size(); j++) {
                Homework homework = homeworks.get(j);    // j번째 과제
                
                // i일차가 해당 과제의 남은 일수 d 이하이고, 
                // i일차에 얻을 수 있는 과제 점수의 최댓값 max보다 해당 과제 점수 w가 더 크다면
                if (i <= homework.d && homework.w > max) {
                    max = homework.w;    // 과제 점수 최댓값 갱신
                    index = j;            // max에 해당하는 과제의 인덱스 갱신
                }
            }
            
            // max에 해당하는 과제의 인덱스가 -1이 아니라면
            // i일차에 얻을 수 있는 과제 점수의 최댓값을 찾은 것임
            if (index != -1) {
                // 얻을 수 있는 점수의 최댓값에 i일차에 얻을 수 있는 점수의 최댓값을 더하기 
                result += max;
                // max에 해당하는 과제를 수행했으므로 과제 리스트에서 인덱스 제거
                homeworks.remove(index);
            }    
        }
        
        System.out.println(result);        // 얻을 수 있는 점수의 최댓값 출력
    }
}