[BaekJoon] 13904 과제 (Java)

1.  문제 링크

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

2.  문제

요약

• 웅찬이는 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있습니다.
• 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없습니다.
• 과제들의 마감일과 점수가 주어질 때, 웅찬이가 얻을 수 있는 점수의 최댓값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 정수인 N이 주어지고 두 번째 줄부터 N개의 줄에 1보다 크거나 같고 1,000보다 작거나 같은 과제 마감일까지 남은 일수인 d와 1보다 크거나 같고 100보다 작거나 같은 과제의 점수 w가 주어집니다.
• 출력: 첫 번째 줄에 얻을 수 있는 점수의 최댓값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    static int N, maxDeadline;
    static LinkedList<Assignment> assignments;
    static void input() {
        Reader scanner = new Reader();
        N = scanner.nextInt();
        assignments = new LinkedList<>();
        maxDeadline = Integer.MIN_VALUE;
        for(int assignment = 0; assignment < N; assignment++) {
            int deadline = scanner.nextInt(), score = scanner.nextInt();
            maxDeadline = Math.max(maxDeadline, deadline);
            assignments.add(new Assignment(deadline, score));
        }
    }

    static void solution() {
        int answer = 0;
        for(int day = maxDeadline; day > 0; day--)
            answer += getMaxScoreInThatDay(assignments, day);
        
        System.out.println(answer);
    }

    static int getMaxScoreInThatDay(LinkedList<Assignment> assignments, int day) {
        int maxIdx = -1, maxScore = 0;
        for(int assignment = 0; assignment < assignments.size(); assignment++) {
            Assignment cur = assignments.get(assignment);
            if(cur.deadline >= day && maxScore < cur.score) {
                maxIdx = assignment;
                maxScore = cur.score;
            }
        }

        if(maxScore == 0) return 0;

        assignments.remove(maxIdx);
        return maxScore;
    }

    static class Assignment {
        int deadline, score;
        public Assignment(int deadline, int score) {
            this.deadline = deadline;
            this.score = score;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 과제들을 나타내기 위해 Assignment라는 클래스를 생성하는데, 이 클래스는 과제 마감일까지 남은 일수인 deadline과 과제의 점수 score를 멤버로 가집니다.
• 입력으로 주어지는 과제들을 assignments라는 LinkedList에 담는데, 이 때 마감일까지 남은 일수 중 가장 오래 남은 일수를 maxDeadline이라는 변수에 담습니다.
• 과제를 수행한지 maxDeadline일째부터 1일째일 때까지 1씩 줄여가며 그 때 수행할 수 있는 과제 중 점수가 가장 높은 과제를 찾습니다.
  • 예를 들어, 과제를 수행한지 5일째라면, 과제의 마감일까지 남은 일수가 1, 2, 3, 4일 중 하나인 경우에는 마감일이 지났기 때문에 수행할 수 없습니다.
  • 그에 반해, 과제의 마감일이 남은 일수가 5, 6일인 과제들은 마감일 내에 존재하기 때문에 그러한 과제들은 수행할 수 있습니다.
  • 이를 이용하여 수행할 수 있는 과제들 중에서 가장 점수가 높은 과제를 찾습니다.
  • 만약 수행할 수 있는 과제가 없다면 그 때 얻을 수 있는 점수는 없기 때문에 0을 더합니다.
  • 수행할 수 있는 과제가 있다면 그 중 가장 점수가 높은 과제를 찾고 그 점수를 얻을 수 있는 점수에 더해주고 해당 과제는 수행하였기 때문에 assigments에서 제거합니다.
• 1일째일 때까지 수행할 수 있는 과제 중 점수가 가장 높은 과제들을 찾고 해당 점수들을 더해나갔다면 더해나간 그 점수가 답이 됩니다.