[백준] (13904) 과제

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

사용 언어 : JAVA

---

---

풀이

마감일이 많이 남은 순으로 정렬한 후, 가장 마지막 날부터 선택할 수 있는 가장 최선의 선택을 고른다.

ex) 일 별 해결할 수 있는 과제 목록
 
6일 째 : 5
5일 째 : 5
4일 째 : 5 60 40 10
3일 째 : 5 60 40 10 30
2일 째 : 5 60 40 10 30 50
1일 째 : 5 60 40 10 30 50 20
6일 째부터 1일 째까지 선택할 수 있는 최고의 가치를 가진 숙제를 선택한다.

 

그리디 알고리즘의 경우 몇가지 팁이 있다고 한다.

• 이번 선택이 다음 선택에 영향을 받지 않도록 만들어 보기
• 뒤에서부터 생각하기

이번 문제의 경우 두 가지 팁 다 적용된 사례라고 볼 수 있다.

 

최종 코드

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

public class Main {
	static int N;
	static int[][] paper;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		paper = new int[N][2];
		
		int day = 0;
		
		for(int i=0; i<N; i++) {
			String[] input = br.readLine().split(" ");
			paper[i][0] = Integer.parseInt(input[0]);	// day
			paper[i][1] = Integer.parseInt(input[1]);	// weight
			day = day<paper[i][0]? paper[i][0]: day;
		}
		
		// "마감일"로 내림차, 점수로 내림차로 1차 정렬
		Arrays.sort(paper, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return (o1[0]==o2[0]? o2[1]-o1[1]: o2[0]-o1[0]);
			}
		});
		
		// 각 일별로 가장 최선의 숙제를 찾을 수 있는 우선순위 큐
		PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2-o1;
			}
		});
		
		// 가장 먼 미래(day)에서 선택할 수 있는 숙제들의 우선순위를 매김
		int j=0, answer=0;
		for(int i=day; i>0; i--) {
			for(; j<N && paper[j][0] >= i; j++) {
				queue.add(paper[j][1]);
			}
			
			if(!queue.isEmpty())
				answer += queue.poll();
		}
		
		System.out.println(answer);
	}
}

---

느낀점

• 그리디는 어렵다..