[알고리즘] 과제

구현 방식

• 이것도 맨 처음에는 간단하게 과제 마감일과 점수를 pair로 묶어서 끝에서부터 탐색
  • 현재 day 보다 값이 크거나 같은것중에 최대값인 점수를 해당 day에서 진행할 과제로 채택
• 위와 같은 방식으로 진행하려고 했다.
• 하지만, 그렇게 하면 day 보다 작은데, 현재 day에서 올수 있는 더 큰 점수를 가진 값을 채택하기 힘들어진다.
  • 예를 들어서 현재 4 일 째를 탐색하고 있는데, (5일 마감, 10) , (4일 마감, 30) 중 5일 마감짜리를 선택하게 돼버림
• 그래서 가능한 일자에서 올수 있는 최대값(우선순위큐) 로 묶어놓는 식으로 진행한다. 예제의 입출력을 통해 보면 아래와 같이 정리를 하는 것이다.

1 : 20
2 : 50
3 : 30
4 : 60 40 10
5 : 
6 : 5

• 그래서 만약에 현재 4 일 째를 탐색하고 있다면, 4 일, 5 일 , 6일 째의 우선 순위 큐의 top 값을 확인하면서 점수를 쌓는다.

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;

const int MAXSIZE = 1001;

void solution(int maxDay, priority_queue<int>* homeworks);

int main()
{
	int N;
	cin >> N;
	// 일별로 점수값 정리
	priority_queue<int> homeworks[MAXSIZE] = {};
	int hwDay, hwScore, maxDay = INT_MIN;
	while (N--)
	{
		cin >> hwDay >> hwScore;
		homeworks[hwDay].push(hwScore);
		maxDay = max(maxDay, hwDay);

	}

	solution(maxDay, homeworks);
	return 0;
}

void solution(int maxDay, priority_queue<int>* homeworks)
{
	int targetDay = 0, score = 0;
	int result = 0;
	for(int currDay = maxDay; 0 < currDay ; currDay--)
	{
		score = targetDay = 0;
		// 현재 Day 에서부터 가능한 날까지, 올 수 있는 최대값 
		for (int day = currDay; day <= maxDay; day++)
		{
			if (homeworks[day].empty()) continue;
			if (score < homeworks[day].top())
			{
				score = homeworks[day].top();
				targetDay = day;
			}
		}
		if (0 < score)
		{
			homeworks[targetDay].pop();
			result += score;
		}
	}

	cout << result;

}