백준 - 13904번 과제

문제

과제 마감일과 과제 점수가 주어질 때
가장 많은 점수를 받도록 과제들을 선택해서 하자!
얻을 수 있는 점수의 최대값은?

생각

그렇다 컴공인이 과제를 하려면 선택과 집중은 필수지 과제 너무 많아ㅋㅋㅋ쿠ㅜㅜ

정답이 되려면 어떻게 선택해야하는지 나와있는 힌트보고 아이디어를 얻었다

과제 점수가 높은 걸 가능하난 많이 하는게 좋으니까
점수순으로 정렬하고 가능한 과제 마감일에 가깝게 과제를 함
이미 다른 과제들로 일정이 다 찼으면 과제 못 함

어떻게 과제 마감일에 가깝게?

0으로 초기화 한 check 배열 사용

마감일이 i날이고, 점수가 w인 과제를 할 수 있는지 보려고 하면

check[i] 보고 0이면 이 날에 아무 과제도 안 한거니까,
이 날 하자! check[i] 를 w로 바꿔줌

0이 아니면 이 날에 다른 더 좋은 점수의 과제를 한 거니까,
for문으로 i-1, i-2, ,,, 하면서 앞에 날에는 할 수 있는지 본다

(잘 이해 안 되시면, 아래 코드를 디버깅하면서
check배열이 어떻게 바뀌는지 보면 바로 이해할 수 있을거에여!~!~)

조심해야 하는 점

마지막에 정답을 출력하기 위해서
check 배열에 선택한 과제들의 점수가 들어있으니까 for문으로 돌아줬는데

이 때 범위를 n으로 해줘서 틀렸었다ㅋㅋㅋ
이렇게 틀린 사람 꽤 있더라구여 질문검색에서 봄 웃기당

가능한 최대 범위인 1000으로 해줘야함

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <functional>

using namespace std;

priority_queue<pair<int, int>> q;
int check[1005];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, result = 0;
	vector<pair<int, int>> info;

	cin >> n;

	for (int i = 0; i < n; i++) {
		int d, w;
		cin >> d >> w;
		q.push(make_pair(w, d));
	}

	while (!q.empty()) {
		pair<int, int> top = q.top();
		q.pop();

		if (check[top.second] == 0) {
			check[top.second] = top.first;
		}else {
			for (int i = top.second; i > 0; i--) {
				if (check[i] == 0) {
					check[i] = top.first;
					break;
				}
			}
		}
	}

	for (int i = 0; i <= 1000;i++) {
		result += check[i];
	}

	cout << result;

	return 0;
}