03.09. 과제[Greedy Algorithm][백준 13904]

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

13904번: 과제

 

Algorithm classification : Greedy Algorithm

 

03.09.1. Problem

Woongchan has many challenges. You can complete one assignment per day, but each assignment has a deadline, so you may not be able to finish all of them. Each task has a score for completing it, but assignments past the due date will not receive points.

 

Woongchan wants to do the task so that he can get the most points. Help Woong Chan to find the maximum number of points he can get.

 

03.09.2. Input limit

The first line is given an integer N (1 ≤ N ≤ 1,000). Two integers d (1 ≤ d ≤ 1,000) and w (1 ≤ w ≤ 100) are given to each of the N lines from the next line. d is the number of days remaining until the due date of the assignment, and w is the score of the assignment.

 

03.09.3. Output

Outputs the maximum number of points that can be obtained.

 

03.09.4. Solution

결정 인자가 점수, 남은 일수 2개입니다. 그리디 알고리즘에서 2개 이상의 인자가 상호작용하여 결과를 도출해내는 문제는 상당히 어려운 문제입니다. 그래서 대부분 2개 이상의 인자더라도 우선순위가 있을 것입니다. 여기서는 점수겠죠. 점수를 우선적으로 보면서 과제를 처리할 수 있는 날 중 최대한 늦게까지 미루어 처리하는 것이 이득일 것입니다. 마치 우리가 실제로 과제를 하는 것처럼요. 여기서도 마찬가지로 Vector element순서를 고민해보셔야 합니다. Sorting하였을 때 무엇을 우선할 것인지 생각하시면 됩니다.

	vector<pair<int, int> > v;
	for(i = 0; i < n; i++){
		scanf("%d %d", &d, &w);
		v.push_back(pair<int,int>(w,d));
		day = max(day, d);
	}
	sort(v.begin(), v.end());
	
	int sum = 0;

여기서 day를 세주는 이유는 아래와 같이 배열의 size를 최대한 적게 잡고자 하는 것입니다. 뭐... 요즘같이 메모리가 넘치는(? : CPU clock에 비해서 넘친다는 것입니다... CPU clock을 높이는 것은 물리적 한계가 있어요) 세상에서는 불필요한 코드일 수도 있겠다는 생각이 듭니다.

	int s[day+1] = {0}, j;
	for(i = n-1; i >= 0; i--){
		for(j = v[i].second; j > 0; j--){
			if(s[j] == 0){
				s[j] = 1;
				sum += v[i].first;
				break;
			}
		}
	}