BOJ 13904 : 과제 [C++]

 

13904번: 과제

 

그리디 문제만 보면 지능이 낮아지는 병이 있어서 힘들게 풀었다

그리디인건 빠르게 눈치챘는데, 어떻게 풀어야 할지 모르겠어서 질문 게시판의 반례를 쳐다보다 아이디어를 얻었다.

 

마감일이 N일 남은 문제는 N일 전에만 해결하면 된다.

마감일이 4일 남은 문제는 1일 차에 하든, 2일 차에 하든, 3일 차에 하든, 4일 차에 하든 상관없단 거다.

'1일 차부터 N일차까지 현재 과제를 집어넣을 수 있는 날이 있는가?'를 따져보고 넣을 수 있다면 답에 점수를 더하자

 

작년에 푼 이 문제와 상당히 유사하다.

10775번: 공항

 

 

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>

#define PII std::pair<int, int>

int N;
PII homeworks[1001];    // deadline, score
int parent[1001];

int findParent(int x) {
    if (parent[x] == x) {
        return x;
    } else {
        return parent[x] = findParent(parent[x]);
    }
}

int main() {
    std::cin >> N;

    for (int i = 0; i < 1001; i++) {
        parent[i] = i;
    }

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

    std::sort(homeworks, homeworks + N, [&](PII a, PII b) {
       if (a.second == b.second) {
           return a.first > b.first;
       } else {
           return a.second > b.second;
       }
    });

    int answer = 0;
    for (int i = 0; i < N; i++) {
        int pDay = findParent(homeworks[i].first);
        if (pDay > 0) {
            parent[pDay] = parent[pDay] - 1;
            answer += homeworks[i].second;
        }
    }

    std::cout << answer << "\n";

    return 0;
}