[C++] 백준 13904번: 과제

🔗 문제

13904번: 과제

13904번: 과제

 

 

🖍 풀이

 

✔️ 최적의 해 구하는 방법

과제 점수가 높은 걸 챙기되, 최대한 마감일에 내면 된다.

 

과제 점수가 높다고 첫날부터 해버리면 안된다.

1 30, 5 100 일때를 생각해보자. 130점을 챙길 수 있는데 100점만 맞을 수도 있다.

 

또 하루에 한 과제만 할 수 있으니 visited[i]로 i 날 과제를 냈는지 안 냈는지 확인해줘야 한다.

 

 

+ 천재같은 사람을 봤다..

입력을 {-d, w} 받으면 비교 함수를 안 만들어도 된다.

 

 

💾  소스

#include <iostream>
#include <queue>
#include <algorithm>
#define MAX  1000

typedef std::pair<int, int> pii;
struct compare
{
    bool operator()(const pii& a, const pii& b)
    {
        if(a.second == b.second)
            return a.first < b.first;
        
        return a.second > b.second;
    }
};

int main()
{
    int N, d, w, answer = 0;
    bool visited[MAX+1] = {false, };
    std::vector<pii> v;
    
    std::cin >> N;
    for(int i=0; i<N; ++i)
    {
        std::cin >> d >> w;
        v.push_back({d, w});
    }
    
    //과제 점수가 높은 순으로 정렬
    std::sort(v.begin(), v.end(), compare());
    
    //과제 점수가 제일 높은 순으로 본다.
    for(const auto& [d, w] : v)
    {
        // 과제 낼 수 있는 당일에 내는데 만약 더 높은 점수가 그 날 냈다면.. 그 전날에 내자.
        for(int i=d; i>=1; --i)
        {
            if(!visited[i]) // i날에 낼 과제가 이미 정해져 있지 않다면
            {
                visited[i] = true;
                answer+=w;
                break;
            }
        }
    }

    std::cout << answer;

    return 0;
}