[BOJ/13904] 과제, c++

🔗 링크

https://www.acmicpc.net/problem/13904

13904번: 과제

🤯 한줄 후기

이무진의 과제곡 노래 좋습니다.

🤷 문제

👩‍💻 풀이

전형적인 그리디 문제이다.

핵심 아이디어는

점수가 가장 큰 과제부터 시작한다 다만 과제는 최대한 마감일에 맞춰서 수행해야한다.

과제는 미루는게 제 맛이지!

처음에 마감 기한 순서대로 정렬해서 푸는 문제인가 하고 고민했는데 wa 를 받아서 점수를 기준으로 정렬해서 생각해보았다.

점수가 가장 큰 과제부터 시작하는 건 맞고, 해당 과제를 마감일에 맞춰서 수행한다는 것을 알아야 풀 수 있다.

구현은 day 배열을 만들어 day[마감기한] ~ day[1] 까지 순서대로 돌면서 비어있는 곳이 있다면 해당 날짜에 수행하는 것으로 표시하고 점수를 더해주었다.

💻 코드

//AC
//BOJ 13904 과제
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
vector<pair<int, int>> v;
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
    return a.second > b.second;
}
int day[1001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N;
    for(int i=0; i<N; i++) {
        int d, w;
        cin >> d >> w;
        v.push_back({d, w});
    }
    sort(v.begin(), v.end(), cmp);
    int maxW = 0;
    for(int i=0; i<N; i++) {
        int curD = v[i].first;
        int curW = v[i].second;
        for(int j = curD; j >= 1; j--) {
            if(!day[j]) {
                day[j] = 1;
                maxW += curW;
                break;
            }
        }
        
    }
    cout << maxW;
    return 0;
}