[백준] 13904번: 과제(그리디)

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

13904번: 과제

코드

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int N = scan.nextInt();	
		int[][] work = new int[N][2];
		int maxScores = 0;	//과제 점수 최댓값
		int days = 0;		// 과제 진행한 날
		for(int i=0; i<N; i++) {
			work[i][0] = scan.nextInt();	// 과제 마감기한
			work[i][1] = scan.nextInt();	// 과제 점수
		}
		
		// 과제 점수 높은순으로 정렬
		Arrays.sort(work, new Comparator<int[]>() {
			@Override	
			public int compare(int[] o1, int[] o2) {
				return Integer.compare(o2[1], o1[1]);
			}
		});
		
		int[] scores = new int[1001];	// 정수 N의 범위 - 1~1000
		for(int i=0; i<N; i++) {		// 과제 점수가 높은 순
			for(int j=work[i][0]; j>0; j--) {	// 과제의 마감일로부터 최대한 늦게 과제 하기
				if(scores[j] == 0) {
					scores[j] = work[i][1];
					break;
				}
			}
		}
		
        	/*
		for(int i=0; i<N; i++) {
			System.out.print(work[i][0] + " " + work[i][1]);
			System.out.println();
		} 
       		 */
		
		for(int i=0; i<scores.length; i++) 
			maxScores += scores[i];
			

		System.out.println(maxScores);
		scan.close();
	}

}

풀이

어제 문제를 풀다가 시간이 없어서 내일풀기로 하고 나머지 풀었는데,, 사실 문제에 대한 접근과 해결법은 간단했는데 어떻게 구현할지에 대해 좀 애를 먹었다.

문제에서 하루에 과제는 하나만 할 수 있고, 과제마다 마감일이 있는데 가장 점수를 많이 받을 수 있도록 과제를 수행해야 한다. 과제 점수의 최댓값을 구해야 한다.

문제의 접근 & 해결은 간단하다.

1) 문제별로 과제 점수가 높은순으로 정렬한다.

2) 과제 점수가 높은순으로 정렬되었으면, 마감일이 많이 남은건 가장 늦게 끝내야한다.

위 두개가 끝이다.

문제와 같이 입력하고, 과제순으로 정렬하면 위 흰색과 같이 나온다.

이때 최댓값은 60 + 50 + 40 + 30 + 5가 되는데, 마감일이 남은 과제(4일)은 가장 마지막에,

마감일이 임박한 과제(2일, 3일)은 가능한 빨리 과제를 해야한다.

일단 과제점수가 가장 높게 나오려면, 과제 점수가 가장 높은순으로 과제를 해야한다.

따라서 과제 점수가 높은순으로 마감일에 최대한 가깝게 탐욕적으로 넣어준다.

 

첫 번째 정렬된 입력부터 보자.

마감일 - 4일 , 점수 - 60점

이 과제는 4일째 끝내도록 설정한다. scores[4] = 60

 

두 번째 높은 점수의 과제를 보자.

마감일 - 2일 , 점수 - 50점

이 과제는 2일째 끝내도록 설정한다. scores[2] = 50

 

세 번째 높은 점수의 과제를 보자.

마감일 - 4일 , 점수 - 40점

이 과제를 4일째 끝내려고 했으나, 이미 4일째 끝내기로한 과제가 존재한다. 

따라서 이 과제는 마감일에 최대한 가깝게 3일에 끝내주도록 한다. scores[3] = 40

 

네 번째 높은 점수의 과제를 보자.

마감일 - 3일 , 점수 - 30점

이 과제를 3일째 끝내려고 했으나, 이미 3일째는 끝내기로 한 과제가 존재한다.(scores[3] = 40)

그래서 이 과제를 2일째에 끝내려고 했으나 마찬가지로 존재한다.(scores[2] = 50)

따라서 이 과제를 첫번째 날에 가장 먼저한다. scores[1] = 30

 

다섯 번째 높은 점수의 과제를 보자.

마감일 - 1일 , 점수 - 20점

이 과제는 무조건 첫번째날에만 할 수 있으나, 위에서 첫번째날에 할수 있는 과제중 최대점수는 30점이다. 따라서 패스

 

여섯 번째 높은 점수의 과제(마감일 - 4일 , 점수 - 10점) 마찬가지 패스한다.

 

마지막 점수

마감일 - 6일 , 점수 - 5점

6일째애는 아무 과제도 하지않으므로 이 과제를 하면된다. scores[6] = 5

 

따라서 최대점수는 60 + 50 + 40 + 30 + 5 = 185점 이 된다.