[JAVA] 13904번: 과제

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

13904번: 과제

✅ 골드 Ⅲ

 

🔶 풀이

알고리즘 분류에는 자료 구조, 정렬, 우선순위 큐라고 적혀있는데 다 필요 없다.

그냥 그리디 알고리즘으로 해결할 수 있다.

 

마감일까지 남은 일수와 과제 점수 두 개를 입력받을 때 마감 기한 중에 가장 긴 날짜를 구한 후에 거꾸로 계산하면 된다.

예제에서는 가장 길게 남은 마감 기한은 6일이므로 6일차부터 1일차로 순서대로 내려가면 된다.

 

6일차: 점수 5점짜리 과제만 있음.

5일차: 과제 없음

4일차: 60, 40, 10점짜리 과제 중에 가장 점수가 많은 60점을 수행

3일차: 마감 기한이 남은 4, 5, 6일차 중에 아직 과제를 수행하지 않은 과제도 생각해야하므로 40, 30, 10점짜리 과제 중에 가장 높은 40점을 수행

 

2일차: 50, 30, 10점짜리 중에 50점 수행

1일차: 30, 20, 10점짜리 중에 30점 수행

 

최종적으로 5 + 60 + 40 + 50 + 30 = 185

 

 

import java.io.*;
import java.util.*;

public class Main {	
    public static class subject{
        int day, score;
		
        public subject (int day, int score) {
            this.day = day;
            this.score = score;
        }
    }
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        int N = Integer.parseInt(br.readLine());
        int maxDay = 0;
        ArrayList<subject> arrList = new ArrayList<>();
		
        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
			
            int d = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
		
            arrList.add(new subject(d, w));
			
            if (maxDay < d) {
                maxDay = d;
            }
        }
		
        int ans = 0;
        int maxScore = 0;
        int idx = -1;
        for (int i=maxDay; i>0; i--) {
            for (int j=0; j<arrList.size(); j++) {
                int sDay = arrList.get(j).day;
                int sScore = arrList.get(j).score;
				
                if (i <= sDay && maxScore < sScore) {
                    maxScore = sScore;
                    idx = j;
                }
            }
			
            ans += maxScore;
			
            if (idx > -1) {
                arrList.remove(idx);
            }
			
            maxScore = 0;
            idx = -1;
        }
		
        System.out.println(ans);
    }
}