boj 13904 과제

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

13904번: 과제

그리디는 많이 안풀어봐서 어렵네요..

이 문제는 정렬 + 그리디 문제입니다.

 

우선 마감일, 과제 점수를 담은 list배열을

1. 과제 점수가 높은 순 (내림차순)
2. 마감일이 적게 남은 순 (오름차순)

으로 정렬합니다.

 

그 다음 과제 점수가 가장 높은 0번 인덱스부터 과제를 진행합니다.

여기서 확인해야할 것은 마감일 안에 과제를 할 수 있는지에 대한 여부입니다.

d일부터 1일까지 visit[d]=true인지 확인해서 해당 일에 과제를 했는지 체크합니다.

과제를 했다면 전날 과제를 했는지 체크하는 방식으로 1일까지 확인합니다.

 

과제를 하지않은 날이 있다면 과제를 진행하고 방문체크 해주면 되고,

d ~ 1일 모두 이미 과제를 한 상태면 해당 과제를 진행할 수 없다는 뜻입니다.

 

#include <iostream>
#include <algorithm>
#define MAX 1000
using namespace std;
typedef pair<int, int> pi;
 
pi list[MAX];
bool visit[MAX + 1];
int N;
 
bool cmp(pi a, pi b) {
    if (a.second == b.second) return a.first < b.first;
    else return a.second > b.second;
}
 
void func() {
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int d = list[i].first;
        for (int j = d; j > 0; j--) {
            if (visit[j]) continue;
            
            visit[j] = true;
            ans += list[i].second;
            break;
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> list[i].second;
    }
    sort(list, list + N, cmp);
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}