13904 - 과제

문제 풀이

아이디어가 생각이 안나서 풀이를 봤는데 생각보다 간단했던 아이디어였다.
아이디어 : 점수가 높은 과목 우선으로 마감일에 최대한 가깝게 끝낸다

1. 점수가 높은 과목 우선으로
   점수가 높은 것부터 내림차순으로 정렬한다.
2. 마감일에 최대한 가깝게
   마감일부터 시작하여 한칸씩 전날로 이동하면서 과제를 하지 않는 날이 있으면 그날에 과제를 한다.
   ex)

   예제코드
   7
   4 60
   4 40
   1 20
   2 50
   3 30
   4 10
   6 5

---

1번 논리 적용(점수 순으로 내림차순)
4 60
2 50
4 40
3 30
1 20
4 10
6 5

---

2번 논리 적용
visited[4]=60 // 4일에는 첫번째 과제를 수행
visited[2]=50 // 2일에는 두번째 과제를 수행
X visited[4]=40// 4일에는 세번째 과제를 수행해야 하지만 O visited[3]=40// 이미 첫번째 과제를 수행하기로 했으므로 3일로 넘어간다.
visited[3]=30 // 3일에 할과제가 이미 있음
visited[2]=30 // 2일에 할과제가 이미 있음
visited[1]=30 // 1일에는 할 과제가 없으므로 1일에 네번째 과제 수행
...
...
...

코드

#include <iostream>
#include<algorithm>
using namespace std;

int N;
pair<int, int> arr[1001];
int visited[1001];
int ans;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> arr[i].second >> arr[i].first;
    }
    sort(arr+1, arr + N+1,greater<>());

    for (int i = 1; i <= N; i++) {
        for (int j = arr[i].second; j > 0; j--) {
            if (j > N) { j = N; }
            if (visited[j]==0) {
                visited[j] = arr[i].first;
                break;
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        ans += visited[i];
    }
    cout << ans;
    return 0;
}