[백준] 13904번 과제 (C++)

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

 

 

이 문제는 N개의 과제가 주어질때 (마감일, 얻을 수 있는 점수)가 주어지며 이때 점수를 많이 받을 수 있는 최댓값을 출력해야 한다.

 

N이 최대 1000이므로 굉장히 작은 숫자이다.

 

즉 O(N^2)으로도 풀린다는 의미이므로 따로 visited라는 배열을 만들었고

 

과제를 점수순으로 정렬한 이후 순차적으로 확인하며 d가 채워지지 않은 경우 true로 채워넣고 만약 채워진 경우 마감일자에서부터 1일까지 확인하여 빈곳이 있는지 확인하여 채워 넣어 점수를 최대한으로 얻을 수 있는 로직을 구성하였다.

 

이 풀이는 시간복잡도가 최대 O(N^2)인 풀이이다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct horse {
    int x;
    int y;
    int dir;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N;
vector<pii> v;
bool visited[1001];

bool compare(pii a, pii b) {
    return a.second > b.second;

    if(a.second == b.second) {
        return a.first > b.first;
    }
}

void solve() {
    sort(v.begin(), v.end(), compare);

    int answer = 0;

    for(int i = 0; i < N; i++) {
        int day = v[i].first;
        int score = v[i].second;

        if(!visited[day]) {
            visited[day] = true;
            answer += score;
        }
        else {
            for(int j = day; j >= 1; j--) {
                if(!visited[j]) {
                    visited[j] = true;
                    answer += score;
                    break;
                }
            }
        }
    }

    cout << answer;
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}