[PS 백준 - 3.12] 13904번: 과제

문제 정보

백준 13904번 - 바로가기

• 난이도: 골드 3
• 알고리즘: 그리디 알고리즘

코멘트

이전 문제 (회의실 배정) 에서 삽질을 해서 그런지 이 문제는 훨씬 쉽게 풀었다.

1. 크기가 최대 1000이라서 먼저 각 날짜별 점수를 담을 배열을 만들었다.
2. 입력을 받은 과제의 날짜에 배열 값이 비었으면 집어넣고, 이미 값이 존재하면 벡터에 값을 대입해두었다.
3. 벡터에서 가장 높은 점수가 첫번째로 오도록 정렬하였다.
4. 벡터에서 과제를 하나씩 꺼내 자신의 날짜에 있는 과제부터 비교를 한다. 해당 날짜의 과제 점수보다 벡터의 과제 점수가 크면 교체가 일어나고, 작으면 그대로 둔다. 그리고 그 앞 날짜의 과제 점수와 비교를 한다. 이 과정을 1일차까지 반복한다. (미끄럼틀처럼 내려가면서 자기보다 작은 점수를 찾으면 자리 교체를 한다.)
5. 1일차까지 지나고 남게 된 과제는 포기한다.

내가 생각한 과정을 그림으로 나타내보면 아래와 같다.

소스 코드

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

using namespace std;

bool compare(pair<int, int> a, pair<int, int> b) {
    if (a.second == b.second) {
        return a.first > b.first;
    }
    return a.second > b.second;
}

int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;

    // 먼저 0으로 다 초기화
    int scores[1000] = { 0, };

    vector<pair<int, int>> vec;

    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        
        if (scores[a - 1] == 0) {
            scores[a - 1] = b;
        }
        else {
            vec.emplace_back(a-1, b);
        }
    }

    sort(vec.begin(), vec.end(), compare);

    int size = vec.size();

    while (size > 0) {
        int score = vec[0].second; // 큰놈부터 나옴!
        int idx = vec[0].first;

        int i = 0;
        while (true) {
            if (idx - i < 0) break;
            if (scores[idx - i] < score) {
                int tp = score;
                score = scores[idx - i];
                scores[idx - i] = tp;
            }
            i++;
            
        }

        vec.erase(vec.begin());
        size = vec.size();
    }

    int cnt = 0;
    for (int i = 0; i < 1000; i++) {
        cnt += scores[i];
    }

    cout << cnt;
}