[Greedy] 13904번 과제

13904번 과제

 

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

 

문제

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

 

입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

 

출력

얻을 수 있는 점수의 최댓값을 출력한다.

 

예제 입력

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

 

예제 출력

185

 

힌트

예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다.

 

해결방법

Greedy Algorithm 유형의 문제이다

 

 

⭐️ 솔루션 ⭐️

소팅 & 그리디 로 문제를 접근해야했다

아래의 두 경우는 성립하지 않는 조건이다

1. 과제 마감일이 급박한 순서
2. 과제 점수가 높은 순서

이 문제에서는 과제를 점수 내림차순으로 정렬 후, 과제의 마감일 중 lastday 를 구하여 날짜를 감소시켜가며 수행가능한 과제를 수행하는 솔루션을 적용해야한다

 

전체적인 흐름은 아래와 같다

1. 과제의 점수와 마감일을 입력받으면서 과제의 lastday 를 구한다
2. 점수를 기준으로 내림차순 정렬을 한다
3. lastday 부터 1일까지 감소하며 해당 날짜에 수행가능한 과제가 있는지 확인한다
4. 수행한 과제는 flag 배열을 통해 방문 처리를 수행해준다

 

시간 복잡도

최대 마감일부터 감소시키며, 과제의 수행 가능 여부를 확인하므로 2중 for문으로 (1000 x 1000) 구현을 할 수 있다. 따라서 시간복잡도는 O(N∗d) 이다

 

 

 

소스코드

문제 해결 시간 : 1h

메모리 : 2124 KB

시간 : 0 ms

#include <iostream>
#include <vector>
#include <math.h>
#include <cstring>
#include <algorithm>
using namespace std;

struct homework {
    int deadline,grade;
    
    homework() { }
    homework(int d,int g) : deadline(d),grade(g) { }
};

bool cmp (homework &h1,homework &h2){
    return h1.grade > h2.grade;
}

int n,d,g,ans,last_day;
bool visited[1001];
vector<homework> v;

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    for(int i=0; i<n; i++){
        cin >> d >> g;
        v.push_back(homework(d,g));
        
        // 과제 마감일이 제일 늦는 날짜
        last_day = max(last_day,d);
    }
    
    // 정렬
    sort(v.begin(), v.end(), cmp);
    
    // 초기화
    memset(visited, false, sizeof(visited));
    ans = 0;
    
    // lastday 부터 수행할 수 있는 과제 중, 점수가 가장 큰 과제부터 수행
    for(int day=last_day; day>=1; day--){
        for(int i=0; i<v.size(); i++){
            // 아직 해당 과제를 수행하지 않았고, 과제의 마감일이 현재 날짜 안에 속한다면
            if(!visited[i] && v[i].deadline >= day){
                ans += v[i].grade;
                visited[i] = true;
                break;
            }
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}