백준 #13904 과제

BOJ #13904 - 과제

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

# 문제 분류

그리디

풀이 접근 방법

  1. 과제는 미룰 수 있다면 미루는게 좋다.
  2. 따라서 과제의 점수대로 정렬을 한 다음, 최대한 미룰 수 있는만큼 미룬다.
  3. 만약 미룰 수 없다면 포기한다.

정말 그리디는 정렬과 선택 두 가지를 적절히 잘 해주는게 중요한 것 같다.

#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int N, arr[1010];
pair<int, int> p[1010];

int main() {
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> p[i].first >> p[i].second;
    }

    sort(p, p + N, [](pair<int, int> &p1, pair<int, int> &p2) {
        return p1.second > p2.second;
    });

    int result = 0;

    for (int i = 0; i < N; i++) {
        for (int j = p[i].first; j > 0; j--) {
            if (!arr[j]) {
                arr[j] = 1;
                result += p[i].second;
                break;
            }
        }
    }

    cout << result;
}