[백준] 13904 - 과제

[문제링크]

13904번: 과제

 

0. 마감일까지 10일남은 과제를 오늘 하는건 괜찮지만, 마감일까지 하루 남은 과제를 10일뒤에 하는것은 불가능하다

  - 가장 먼 마감일부터 그리디하게 최고 점수의 과제를 선택한다

 

1. 과제를 마감일 내림차순으로 정렬한다

 

2. 최고 점수의 과제를 빠르게 선택하기 위해 priority queue 사용

 

3. 각 날짜별로, 해당 날짜 마감의 과제를 priority queue에 넣고, 최고 점수의 하나만 꺼내서 누적한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		int[][]assign = new int[N][2];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			assign[i][0] = pint(st.nextToken());
			assign[i][1] = pint(st.nextToken());
		}
		
		Arrays.sort(assign, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o2[0]-o1[0];
			}
		});
		
		PriorityQueue<Integer>pq = new PriorityQueue<>(Comparator.reverseOrder());
		int totalScore=0;
		
		int today = assign[0][0];
		int i=0;
		while(today!=0) {
			while(i<N && assign[i][0]==today) {
				pq.add(assign[i][1]);
				i++;
			}
			
			//날짜 갱신
			today--;
			if(!pq.isEmpty())totalScore+=pq.poll();
		
		}
		
		System.out.println(totalScore);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
	
}

결과 화면