백준 13904 과제 (C++)

13904번: 과제

정렬을 이용한 문제이다. 문제에서 주어지는 점수와 마감일을 벡터에 저장을 하는데 이때 마감일 기준 내림차순으로 정렬을 하기 위해 위치를 바꿔 저장을 해준다. 그 후 반복문을 돌면서 배열 cost에 마감일 기한부터 1일까지 중 빈 값을 찾아 점수를 저장해주었고 이를 반복했다. 이렇게되면 점수가 큰 과제부터 등록을 하여 최댓값을 구할 수 있게 된다. 그 후 cost 전체를 돌면서 값을 더해 출력해주었다.
어렵지 않게 풀 수 있었다. 처음에는 단순 dfs로 풀었는데 바로 시간 초과가 나서 정렬을 사용해야 한다는 점을 알 수 있었다. 시간이 걸린 부분은 정렬을 이용한다는 점은 추리해낼 수 있었는데 어떤 기준으로 할 지 생각해내는데 좀 걸렸다. 풀고 나서 보니 내림차순으로 정렬을 하다 보니 우선순위 큐를 이용할 수 도 있겠다는 생각이 들었다. 정렬 문제의 경우 기준이 중요하다는 점을 인지해두자.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, result = 0;
vector<pair<int, int>> v;
int cost[1001];

void solution() {
    sort(v.rbegin(), v.rend());

    for (int i = 0; i < N; i++) {
        int c = v[i].first;
        int deadline = v[i].second;

        for (int j = deadline; j > 0; j--) {
            if (cost[j] == 0) {
                cost[j] = c;
                break;
            }
        }
    }

    for (int i = 1; i <= 1000; i++) {
        result += cost[i];
    }

    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    int a, b;
    for (int i = 0; i < N; i++) {
        cin >> a >> b;
        v.push_back({ b,a });
    }

    solution();

    return 0;
}