[백준 13904번] 과제 (java)

13904번: 과제

 

그리디 문제이다.

N일째부터 1일째까지 거꾸로 돌면서, n일째에 할 수 있는 과제들 중 가장 점수가 큰 과제를 처리한다.

 

 

먼저, 6일째 처리할 수 있는 과제는 5점짜리 과제 하나이다. 따라서 5점짜리 과제를 한다.

sum = 5

 

 

 

그 다음 5일째 처리할 수 있는 과제는 하나도 없다. 이미 5점짜리 과제를 해결했기 때문이다.

 

 

4일째에 처리할 수 있는 과제는 10점짜리, 40점짜리, 60점짜리가 있다. 

이 중에서 가장 큰 점수를 가지는 과제는 60점짜리 과제이다. 따라서 4일째에는 60점짜리 과제를 처리한다.

sum = 65

 

 

3일째에 처리할 수 있는 과제는 10점짜리, 30점짜리, 40점짜리가 있다.

이 중에서 가장 점수가 큰 과제는 40점이므로 3일째 되는 날에는 40점짜리 과제를 처리한다.

sum = 105

 

 

2일째에 할 수 있는 과제는 10점짜리, 30점짜리, 50점짜리가 있다. 

이 중에서 가장 점수가 큰 과제는 50점짜리이다. 따라서 2일째에는 50점짜리 과제를 처리한다.

sum = 155

 

 

마지막으로 1일째 되는 날, 할 수 있는 과제는 10점짜리, 20점짜리, 30점짜리가 있다.

이 중에서 가장 점수가 큰 과제는 30점이므로, 1일째에는 30점짜리 과제를 처리한다.

sum = 185

 

 

 

따라서, 과제는 1일째에 30점, 2일째에 50점, 3일째에 40점, 4일째에 60점, 6일째에 5점짜리를 처리해서

총 185점을 얻을 수 있다.

 

 

 

 

전체 코드 : 

	import java.io.*;
	import java.util.*;
	public class n13904 {
	static int N;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	N = Integer.parseInt(br.readLine());
	List<Homework> list = new ArrayList<>();
	int maxDay = 0;
	for (int i = 0; i < N; i++) {
	String[] input = br.readLine().split(" ");
	int d = Integer.parseInt(input[0]);
	int w = Integer.parseInt(input[1]);
	list.add(new Homework(d, w));
	maxDay = Math.max(maxDay, d);
	}
	int sum = 0;
	for (int i = maxDay; i >= 1; i--) {
	Homework ans = new Homework(0, 0);
	for (Homework hw : list) {
	if (hw.d >= i) {
	if (ans.w < hw.w) {
	ans = hw;
	}
	}
	}
	sum += ans.w;
	list.remove(ans);
	}
	bw.write(sum + "\n");
	bw.flush();
	}
	static class Homework {
	int d, w;
	Homework(int d, int w) {
	this.d = d;
	this.w = w;
	}
	}
	}

view raw 13904.java hosted with ❤ by GitHub