백준 13904번 : 과제

문제 링크 : https://www.acmicpc.net/problem/13904

13904번: 과제

 문제 설명 

과제의 남은 일수와 과제 점수가 주어질때 가장 많은 점수를 얻을수 있는 경우의수 .

 

 알고리즘 

1. 점수가 높은순으로 정렬한다

4	2	4	3	1	6
60	50	40	30	20	5

2. 예제를 예로들면 6일 차부터 얻을수있는 최대 점수를 구한다

6일차 - 5점           3일차 - 40점 (2일남은 과제는 3일차때 못얻으므로.)

5일차 - 0점           2일차 - 50점

4일차 - 60점         1일차 - 30점

 

 코드 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
bool cmp(pair<int,int> a,pair<int,int> b) {
    return a.first > b.first;
}
 
int main() {
    vector<pair<int, int>> p;
 
    int N;
    cin >> N;
    int Size = 0;
 
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        p.push_back(make_pair(b, a));
        
        
        Size = max(Size, a);
    }
 
    // 내림 차순 정렬 
    sort(p.begin(), p.end(), cmp);
 
    vector<int> ans;
 
    for (int i = Size; i >= 1; i--) {
 
        for (int j = 0; j < N; j++) {
            
            //과제 점수를 얻을 수있으면 얻고 break
            if (p[j].second >= i) {
                ans.push_back(p[j].first);
                p[j] = make_pair(0, 0);
                break;
            }
        }
    }
 
    int sum = 0;
    for (int i = 0; i < ans.size(); i++) {
        sum += ans[i];
    }
 
    cout << sum;
 
 
 
 
}