[백준] 13904 과제 - Java

 

 

 

그리디와 우선순위 큐 자료구조를 사용해 풀 수 있다.

 

우선순위 큐는 그냥 쓰면 되는데.. 그리디는 어떻게 사용해야 할까?

 

일단 객체 하나 만들고 점수 내림차순으로 정렬하자.

 

그 후 계산을 시작한다. 하루에 과제 하나를 끝낼 수 있으니, 기간이 많이 남은 과제는 최대한 나중에 하면 된다.

 

점수에 대해 정렬이 된 상태라서, 이렇게 작성하면 고득점을 얻을 수 있다.

 

 

 

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

public class Main {	

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		

		int N = Integer.parseInt(br.readLine());

		PriorityQueue<Assignment> pq = new PriorityQueue<>();

		StringTokenizer st;

		for(int i=0; i<N; i++){
			st = new StringTokenizer(br.readLine());
			pq.add(new Assignment(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));			
		}

		int[] ans = new int[1001];

		for(int i=0; i<N; i++){
			Assignment tmp = pq.poll();
			for(int j = tmp.left; j>0; j--){
				if(ans[j] == 0){
					ans[j] = tmp.score;
					break;
				}
			}
		}

		int sum = 0;

		for(int i=0; i<1001; i++){
			sum = sum + ans[i];
		}

		System.out.println(sum);

	}
}

class Assignment implements Comparable<Assignment>{
	int left;
	int score;

	Assignment(int a, int b){
		left = a;
		score = b;
	}

	public int compareTo(Assignment o2){
		if(score > o2.score){
			return -1;
		}else{
			return 1;
		}
	}
}