[자바]백준 13904번 과제 [그리디][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

 

그리디 문제는 얼핏 보고, 개념을 공부하면 쉽게 단순해서 쉽게 생각이 든다.

하지만 만만하게 볼 알고리즘이 아닌 것 같다.

매 순간 올바른 방법으로 선택하고 정렬이 필요하면 올바른 방법으로 정렬을 해줘야 한다.

실버, 골드 문제를 풀고 이젠 실버는 그냥 맞추겠지 하고 문제를 풀다. 난 '똥이야'하고 좌절한 적이 최근 들어 있다...

 

많이 풀다 보면 느는 것일까?

우선 단기간에 많이 푸는 건 중요한 것 같다.

 

 

문제

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

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

 

입력

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

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

 

출력

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

 

 

예제

 

힌트

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

 

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 정렬
• 우선순위큐

 

문제 설명

현재 문제는 웅찬이가 마감 기간이 다양한 과제들을 해야 하는데 기간 내에 다 못할 수도 다 할 수도 있는데, 이때 과제마다 웅찬이가 받을 수 있는 점수가 다르다.

이때, 마감 기간과 각 점수가 다른 과제 들을 어떤 순서로 해야 가장 높은 점수를 받을 수 있냐는 문제이다.

 

해설

이 문제를 보고 실제로 내가 저 상황이면, 내가 어떤 식으로 순서를 정할까를 먼저 생각해 봤다.

나 대학교에서 놀기만 하고 공부 안 했는데? 내가 저런 걸 짰었나? 그러고 보면 대학교 때 과제를 최대한 미룬 게 여기서 사용되네..

아무튼, 가장 높은 점수를 먼저 나열하고 그걸 기간 내에 최대한 뒤로 미룰 수 있을 만큼 미루고 기간이 임박한 거 먼저 했을 것 같다. 

즉, 이 한 문장에 이 문제의 핵심이 다 포함되어 있다.

1. 우선 받을 수 있는 점수가 높은 순대로 나열 (점수 기준 내림차순)
2. 가장 높은 순대로 최대한 마감 마지막에 하기(마감 마지막에 해야 할 과제가 있으면 마감 전날 하기)

나는 해당 날짜에 마감이 됐다는 표시를 boolean 배열을 사용해서 표시했다.

 

해설 (보충 설명, 생략 가능)

여기서 1번은 그래 그럴 수 있지 하고 넘어갈 수 있겠지만, 2번에서 왜 마감 마지막에 해야 하며, 마감 마지막에 할 과제가 있으면 그 전날로 잡아야 하는 거지? 그 전날도 해야 할 과제가 있지 않을까? 생각할 수 있다.

 

하나하나씩 생각해 보자

우선, 왜 과제를 최대한 마감날 마지막에 해야 하나? 

 

 (A (2일) > B(1일) 과제점수 가정하기)

 

우선 현재 가장 높은 순대로 나온 과제는 제일 높은 점수니까 반드시 해야 한다.  

근데, A과제를 마감날까지 미루지 않고 맨 첫날 했다고 가정해 보자, 그럼 그다음 높은 점수인 B과제가 마감날이 첫날까지면 A과제를 마감날까지 미뤘으면 A + B를 받았을 텐데, A를 첫날 해버려서 A점수만 받게 된다. 그래서 최대한 미뤄서 해야 한다.

 

 (A (2일) > B(2일) > C(1일) 과제점수 가정하기)

 

그다음, 왜 마감 마지막에 할 과제가 있으면 마감 전날로 잡아도 되는 것일까?

여기서 중요한 건 B보다 C가 과제점수가 높다는 것이다. 그래서 A가 2일째 하고 B가 2일째는 A가 있으니 1일째로 넘어가도 C를 하는 것보다 B를 하는 게 더 중요하기 때문이다.

 

코드

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int T = Integer.parseInt(br.readLine());
        int[][] arr = new int[T][2];
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());       
            int d = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            arr[i][0] = d;
            arr[i][1] = w;
        }
        
        Arrays.sort(arr, ((x, y) -> y[1] - x[1]));
        
        boolean[] ck = new boolean[1001];
        
        int point = 0;
        for (int i = 0; i < arr.length; i++) {
            int d = arr[i][0];
            int w = arr[i][1];
            for (int j = d; j > 0; j --) {
                if (!ck[j]) {
                    point += w;
                    ck[j] = true;
                    break;
                }
            }
        }
                                 
       bw.write(point+ "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}