아이디어

점점 알아가는 것 중 하나는 예제를 풀어보면서 힌트를 얻고 그것을 공식으로 만들어 보는 것이 가장 중요한 것 같다.

우선 예제를 보고 그 데이터를 분석하는 것을 첫번째로 했다.

그러기 위해서는 데이터의 특징을 분석해야 했는데, 나는 이 기준을 먼저 남은 날짜로 생각해 보았다.

이 경우 남은 날짜가 별로 안남은 과제부터 생각해 간다면, 최대 점수에 도달할 방법을 생각하는것이 불가하였다.

반대로 가장 뒤의 과제부터 생각해 보면, 만약 겹치는 날짜가 없는 경우에는 그냥 제외시켜도 될 것 같았다.
(예를들면 가장 뒤의 과제가 6일 남았고 6일남은 과제가 더이상 존재하지 않을 때)

이 경우에는 겹치는 경우가 가장 문제가 되었다.

이 겹치는 경우를 해결하기 위해, 뒤에서 부터 다시 차근차근 예시에 대입하여 풀어보았는데 그 결과 가장 높은 점수부터 해결하면 된다는 해법을 얻었다.

단, 이때 해당 날짜에서, 이미 기간(d-day)가 지나버린 과제들은 고려하지 않아야 할 것이다.

즉, 앞이 아닌 뒤에서부터 생각한 조건에 맞게 해결해 나가야 할 것이다.

해법

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

int main() {
	int homework_num;
	vector<pair<int, int>> homework, temp;

	cin >> homework_num;
	for (int i = 0; i < homework_num; i++) {
		int x, y;
		cin >> x >> y;
		homework.push_back({ x, y });
	}
	sort(homework.begin(), homework.end());

	for (int day = homework.back().first; day > 0; day--) {
		if (homework.empty())
			break;
		int max_score_index = homework.size() - 1;
		int max_score = homework[max_score_index].second;

		for (int i = max_score_index; homework[i].first >= day; i--) {
			if (max_score < homework[i].second) {
				max_score = homework[i].second;
				max_score_index = i;
			}
			if (i == 0)
				break;
		}
		if (homework.back().first >= day) {
			temp.push_back(homework[max_score_index]);
			homework.erase(homework.begin() + max_score_index);
		}
	}
	// homework에서 뒤에서부터 day보다 작은것들 (기한이 지난것들)은 고려하지 않는다.
	
	int max = 0;
	for (int i = 0; i < temp.size(); i++)
		max += temp[i].second;

	cout << max;

	return 0;
}

주의점

주의점은 대부분 극단적인 것을 대입했을 때 발견 할 수 있다. 예를들면 데이터가 1개이거나, ... 하는 것 말이다.

1) i==-1

코드를 완성하고 가장 처음 발견한 오류이다

for (int i = max_score_index; homework[i].first >= day; i--)

위와 같은 코드에서 만약 해당 for문이 i==0까지 작동한다면, i--에 의해서 i==-1이 되어 버리게 된다.

즉, 조건검사 부분에서(homework[i].first >= day) 참조를 잘못해 버리기 때문에 오류가 발생한다.

따라서 다음과 같은 코드를 추가해 주었다.

if (i == 0)
	break;

이때, for문의 남은 부분이 있을까 하는 걱정이 있었지만, 잘 생각해 보면 i가 0이 되었다는 것은 조건검사 부분에서 더 이상 day보다 크거나 같은 날짜가 더이상 존재하지 않는다는 것이므로, 제출기한이 지난 과제 말고는 남은 과제가 없다는 뜻이다.

즉, 바로break를 해주어도 무관하다고 생각하였다.

2) empty()

두번째로 발견한 오류이다.

예제는 통과를 했지만 제출시 런타임 오류가 발생하였는데, 그 이유는 코드 중간에 homework.erase()를 해주다가 homework가 비어버리는 경우를 고려하지 않았기 때문이다.

따라서 위의 코드처럼

if (homework.empty())
	break;

를 추가해 주었다.