백준 - 13904번 : 과제 (C++)

풀이 방법 : 우선순위 큐

처음에는 특정 날짜까지 얻을 수 있는 점수의 최댓값들을 갱신해나가는 DP 방식으로 풀어볼까 생각했으나, 그렇게 하려면 특정 날짜에 어떤 과제를 수행하였는지도 기록, 비교 해야하기에 복잡할 것 같았다.

그래서 생각해낸게 어떤 날짜에 어떤 과제를 수행할 것인지 계획표를 짜는 방식이었다. 가장 높은 점수를 가진 과제부터 고려해가면서 각 날짜에 과제를 배정하는 것이다.

우선적으로 데드라인으로 정해진 날짜에 그 과제를 배치하되 만약 해당 날짜에 이미 수행하기로 계획한 과제가 이미 있을 경우, 그 전날부터 첫째날까지 역순으로 아직 계획한 과제가 없는 날짜를 찾아서 배치해주면 된다.

왜 역순으로 해야하는가에 대한 답은, 1일 과제는 첫째날에만 수행가능하고, 4일 과제는 1,2,3,4번째 날에 다 수행이 가능하다는 것을 생각해보면 당연한 일일 것이다.

#include <iostream>
#include <queue>

using namespace std;

struct Info
{
    int Date;
    int Score;
};

struct cmp
{
    bool operator() (const Info& Src, const Info& Dest)
    {
        return Src.Score < Dest.Score;
    }
};

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

    int N;
    cin >> N;

    int MaxDate = 0;
    priority_queue<Info, vector<Info>, cmp> pqInfo;
    for(int i = 0;i<N;++i)
    {
        Info Input;
        cin >> Input.Date >> Input.Score;
        pqInfo.push(Input);
        MaxDate = max(MaxDate, Input.Date);
    }

    int Score = 0;

    vector<int> vecScore(MaxDate + 1, -1);
    while (!pqInfo.empty())
    {
        Info Cur = pqInfo.top();
        pqInfo.pop();

        if (vecScore[Cur.Date] == -1)
        {
            vecScore[Cur.Date] = Cur.Score;
        }

        else
        {
            for (int i = Cur.Date - 1; i >= 1; --i)
            {
                if (vecScore[i] == -1)
                {
                    vecScore[i] = Cur.Score;
                    break;
                }
            }
        }
       
    }

    for (int i = 1; i <= MaxDate; ++i)
    {
        if(vecScore[i] != -1)
            Score += vecScore[i];
    }

    cout << Score;
}

생각보다 여러가지 풀이가 나올거 같다 나중에 또 풀어봐야겠다.