BOJ 13904 과제

https://www.acmicpc.net/problem/13904
시간 1초, 메모리 256MB
input :

• N (1 ≤ N ≤ 1,000)
• d (1 ≤ d ≤ 1,000) w (1 ≤ w ≤ 100) [d는 과제 마감일까지 남은 일수 w는 과제의 점수]

output :

• 점수의 최댓값을 출력

조건 :

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

---

하루가 지날 때 마다 무엇을 해야할 지 판단을 해야 하나 싶었는데, 그럴 경우 날짜 마다 가장 큰 값을 고르다 보면 다른 값을 놓치는 경우가 발생할 수 있다.

다른 방법들 중, 하루하루 지나는 것이 아닌 | 현재 부터 마감일 까지의 과제 제출 계획을 세우는 방식으로 하는 것이 좋을 것 같다.

과제 마감일 까지 남은 일 수 중 가장 큰 값은 1000이다.
1000짜리 배열을 만들어 각 날 짜마다 해야 할 과제의 점수를 넣는다.
그리고 마지막에 이 값을 더하도록 하자.

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

이것을 점수의 내림차순으로 정렬을 한 후에.
각 값을 할 날짜가 존재하는지 확인을 해야 한다. 자신이 하려는 날짜에 이미 다른 과제가 있다면 날짜 - 1을 해가면서 확인을 하다가 이 값이 -1 즉 0보다 작아지면 포기 한다.
이를 while문으로 나타냈다.

그리고 중간에 data[cnt] != 0을 조건으로 거는 바람에 에러가 발생했는데 이를 방지하기 위해 cnt >= 0을 먼저 걸리게 한다.
그러면 연산자 우선순위로 인해 앞에 거를 먼저 판별 하기에 상관이 없어진다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

class Problem implements Comparable<Problem>{
    int day, score;

    public Problem(int day, int score){
        this.day = day;
        this.score = score;
    }

    @Override
    public int compareTo(Problem o){
        return o.score - this.score;
    }
}

public class BOJ_13904_assignment {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[] data = new int[1000];
    static ArrayList<Problem> problem = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++){
            String[] temp = br.readLine().split(" ");
            problem.add(new Problem(Integer.parseInt(temp[0]), Integer.parseInt(temp[1])));
        }

        Collections.sort(problem);
        for (Problem item : problem){

            int cnt = item.day - 1;
            while (cnt >= 0 && data[cnt] != 0) {
                cnt--;
            }

            if (cnt < 0)
                continue;

            data[cnt] = item.score;
        }

        int sum = 0;
        for (Integer item : data)
            sum += item;

        System.out.println(sum);
    }
}