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

📕문제

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

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

---

📕입력

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

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

---

📕출력

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

---

💡문제 해석

이 문제도 대표적인 greedy 탐욕 법 문제이다. 우선 입력받은 d와 w를 다음과 같은 방법으로 정렬했다.

• 이득이 큰 순서대로 정렬.
• 만약 이득이 같다면 과제 마감일이 큰 순서대로 정렬.

내가 처음에 접근한 방법은 마감일대로 딱딱 넣는다. (같은 마감일이 있다면 이득이 큰 것)

그럼 각 마감일마다 과제가 들어갈 것이다. 그러고 이제 선택받지 못한 과제들 중에서 선택한 과제들 중 가장 작은 것과 선택받지 못한 과제들 중에서 가장 큰 것을 바꿔주는 전략을 선택했지만, 어떤 이유에서인지 통과하지 못했다.

그래서 반례를 찾으려고 애를 써봤지만 찾지 못했다..

그래서 다시 생각해낸 방법이 마감일에서 가장 가깝게 과제를 할당하는 것이다.

테스트 케이스를 입력 후 정렬하면 이러한 순서가 된다.

1.4,60에서 마감일을 4로 정하고, visit [4]가 true라면 넘어가고, false라면 다음과 같은 과정을 실행

• sum에다가 60을 더하고 visit [4]를 true로 바꿔줌. 

2.2,50에서 마감일을 2로 정하고, visit [2]를 검사.

• 만약 True라면 넘어감.
• False라면 sum에다가 50을 더하고 visit[2]를 true로 바꿔줌.

이런 식으로 진행하면 각 과제가 그 과제의 마감일과 최대한 가까운 날짜에 배정할 수 있으며, 애초에 처음부터 과제의 이득이 큰 순서대로 정렬했기 때문에, 최적의 해가 나올 것이다.

 

👀구현

1. 입력받은 자료들을 내가 원하는 대로 정렬하기

2. 나는 pair를 이용해서 deadline과 profit을 한꺼번에 저장했음.

3. 마감일에 가깝게 과제를 배정하기.

📃코드

//백준 골드3 13904 과제
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, day = 1, sum = 0;
vector<int> finish, score;
vector<pair<int, int>> p, np;
vector<int> visit(1001, 0);
bool cmp(pair<int, int> &a, pair<int, int> &b) //pair를 sort하기 위한 함수.
{
    //우선 이득이 큰 순서대로 정렬을 한다. 만약 이득이 같다면 과제 마감일이 큰 순서대로 정렬
    if (a.second == b.second)
    {
        return a.first > b.first;
    }
    else
    {
        return a.second > b.second;
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int deadline, profit;
        cin >> deadline >> profit;
        p.push_back(make_pair(deadline, profit));
    }
    sort(p.begin(), p.end(), cmp);
    int end_day = 0;
    for (int i = 0; i < n; i++) 
    {
        end_day = p[i].first; //과제의 마감일을 end_day로 정한다.
        int score = p[i].second; //과제의 점수를 scroe로 지정.
        for (int j = end_day; j >= 1; j--) //마감일부터 하루씩 깎아서 과제를 넣는다.
        {
            if (visit[j] == true) //만약 j가 day라고 생각하면 편함. 해당 날에 이미 과제가 배정되었다면 넘어감.
            {
                continue;
            }
            else //만약 해당 날에 과제가 배정되지 않았다면 
            {
                sum += score; //과제의 점수를 더하고
                visit[j] = true; //해당날에는 풀어야할 과제가 선택되었다는것을 알린다.
                break;
            }
        }
    }
    cout << sum;
}

 

✔느낀 점

• 항상 내가 풀었던 알고리즘이 틀렸다고 인정하고 고치는 것은 쉽지가 않은 것 같다. 하지만 틀렸다고 느꼈을 때 처음부터 다시 짜는 과감함이 필요하다고 느꼈다.
• 알고리즘적으로는 어렵지 않았다. 그나마 조금 고심해서 생각한 것이 visit배열을 만든 것