[BOJ] 백준 13904번 과제 (Java)

#13904 과제

난이도 : 골드 3

유형 : 그리디

13904번: 과제

▸ 문제

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

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

▸ 입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

▸ 출력

얻을 수 있는 점수의 최댓값을 출력한다.

 

문제 풀이  

그리디 일반 유형 문제로 탐욕적인 접근 방식을 잘 설정하여 알고리즘을 설계하면 된다. 방법으로는 여러가지가 있다.

1. 높은 점수 순대로 가장 마감일에 가깝게 풀이를 하기
2. 마감일 d일동안 점수를 많이주는 순대로 d개의 문제 풀기

 

두 가지 케이스 중 어느 것으로 풀이를 해도 상관없다. 두 가지 방식 모두 최적해를 포함하는 그리디 방식이기 때문이다.

 

1번의 경우, 높은 점수 순대로 가장 마감일에 가깝게 풀이를 함으로써 다른 문제들이 (1~마감일-1)에 풀 수 있도록 가장 큰 범위를 제공해주므로 그리디하다.

 

2번의 경우, 가장 마감일이 빠른 순대로 문제를 담아준 다음에 풀 수 있는 문제가 현재 마감일(d)를 초과할 경우 최소 힙을 사용하여 가장 적은 점수를 주는 문제를 빼주기 때문에 그리디하다.

 

풀이 코드 

1번 그리디 방식

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

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());
		
		StringTokenizer st;
		List<int[]> list = 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());
			
			list.add(new int[] {d,w});
		}
		
		Collections.sort(list, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o2[1]-o1[1];
			}
		});
		
		int[] check = new int[1001];
		for(int[] p : list) {
			for(int i=p[0]; i>0; i--) {
				if(check[i]==0) {
					check[i] = p[1];
					break;
				}
			}
		}
		
		int total =0;
		for(int num : check) {
			total += num;
		}
		System.out.println(total);
	}
}

 

2번 그리디 방식

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

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());
		
		StringTokenizer st;
		List<int[]> list = 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());
			list.add(new int[] {d,w});
		}
		
		Collections.sort(list, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0]-o2[0];
			}
		});
		
		Queue<Integer> q = new PriorityQueue<>();
		for(int[] p : list) {
			q.add(p[1]);
			if(q.size() > p[0]) {
				q.poll();
			}
		}
		
		int total=0;
		while(!q.isEmpty()) {
			total+=q.poll();
		}
		System.out.println(total);
	}
}