백준 13903 - 과제 (C++)

 

 

과제의 목록과 마감기한이 주어졌을 때, 얻을 수 있는 최대 점수를 구하는 문제이다.

하나의 과제를 해결하는데 하루의 시간이 걸리기 때문에, 특정 과제를 해결하면 다른 과제를 해결할 수 없게 될 수도 있다.

이러한 상황에서, 최적의 과제 목록을 탐색하여 점수의 최대값을 구하는 문제이다.

 

문제 풀이

이 문제는 아이디어를 필요로 하는 그리디 문제이다. 

하지만, 아이디어를 떠올리기 어려운 문제는 아니다.

 

먼저 생각해보자. 모든 과제를 해결할 수 없고, 특정 과제만을 해결할 수 있다면 어떤 과제를 고르는게 베스트일까?

당연히 점수를 가장 많이 주는 과제를 해결하는 것이 베스트일 것이다.

 

하지만, 점수만 많이 준다고 무작정 먼저 해결해서는 안된다.

모든 문제에는 마감기한이 있다.

어떤 과제는 1일이 남았는데 60점을 주고, 어떤 과제는 2일이 남았는데 80점을 준다고 가정해보자.

 

이 상황에서, 두 번쨰 과제가 점수를 더 많이준다는 이유로 먼저 해버리면, 첫번째 과제는 해결하지 못한채로 총 80점을 받게 된다.

 

하지만, 첫번째 과제를 먼저 해결하게 된다면 두 번째 과제도 다음 날 해결할 수 있기 때문에 총 140점을 받게 된다.

그러므로, 무작정 점수가 높다고 먼저 해결하는 것이 아니라, 마감기한도 고려하여 우선순위를 두어야 한다.

마감기한이 오래남았다면, 최대한 마감기한에 가깝게 해결하는 것이 이상적일 것이다.

 

그렇다면 어떻게 문제를 해결해야 할까?

 

본인은 먼저 일수별로 해결할 과제를 저장하는 배열을 만들었다.

주어진 과제중 가장 긴 마감기한이 10일이라고 치면, 10개의 원소를 담는 배열을 만든 뒤, 각 원소에는 i일차에 해결할 과제를 저장하였다.

 

이후, 과제 목록을 점수순으로 정렬한 뒤, 가장 높은 점수를 주는 과제부터 확인하며 마감기한에 최대한 딱 맞게 배열에 저장해주었다.

 

마감기한이 3일인 과제인데, 이미 3일차에 해결할 문제가 저장되어 있다면 2일차에 해결하도록 하고, 만약 2일차에도 해결해야 할 문제가 저장되어 있다면 1일차에 하도록 하였다. 마찬가지로 1일차에도 저장되어있다면? 현재 과제는 버려도 되는 것으로 판단하고 해결하지 않도록 하였다.

 

그림을 보며 이해해보자. 입력은 아래와 같이 가정해보겠다.

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

  

 

위의 배열은 n일차에 해결할 과제를 저장할 배열이고, 아래 배열은 주어진 입력을 점수순으로 정렬한 상태이다.

아래의 배열중 위의 값은 마감기한이고, 아래의 값이 점수이다.

 

이 상황에서, 첫번째 원소를 확인해보자. 

마감기한이 4일이고 점수가 60점이다. 이 과제는 마감기한에 최대한 가깝게 해결하는 것이 좋기 때문에, 4일차에 배당해주도록 하겠다.

배열에는 점수만 저장해주었다. 다음 두 번째 과제를 보자. 마감기한은 2일이다. 그러므로 2일차에 배정해주겠다.

다음 세 번째 과제도 보자. 마감기한이 4일이기 때문에, 4일차에 배정을 해주어야 하지만, 4일차엔 이미 배정된 과제가 있다. 그러므로, 4일차보다는 하루 빠른 3일차에 배정을 해주도록 하겠다.

다음 4번째 과제를 보자. 마감기한이 3일이 남았는데, 3일차에는 과제가 배정되어 있다. 그러므로 2일차에 배정해야 하지만, 2일차에도 이미 과제가 배정되어 있다. 그러므로 해당 과제는 1일차에 배정해 줄 것이다.

5번째 과제는 1일차에 배정을 해주어야 하지만, 1일차에 이미 과제가 배정되어 있다. 1일보다 더 빠른 날짜에 과제를 해결할 수는 없기 떄문에, 5번째 과제는 버릴 것이다.

 

6번째과제도 마찬가지이다. 마감기한이 4일짜리인데, 4,3,2,1차 모두 과제가 배정되어있으므로 6번째 과제도 버려야 한다.

 

마지막 7번째 과제는 아래와 같이 배정할 수 있다.

 

이렇게, 해결할 과제를 모두 배정하였고, 총 점수의 합은 185점이 된다.

 

풀이 코드

Init();

int NumOfHW = 0;
std::cin >> NumOfHW;

std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::less<std::pair<int, int>>> Queue;

int MaxDeadLine = 0;

for (int i = 0; i < NumOfHW; i++)
{
    int DeadLine = 0;
    int Grade = 0;
    std::cin >> DeadLine >> Grade;

    Queue.push({ Grade, DeadLine });

    MaxDeadLine = std::max(DeadLine, MaxDeadLine);
}

먼저, 과제의 수를 입력받았다.

이후, 우선순위 큐에 입력받을 과제를 {점수, 마감기한} 페어로 삽입해주었다.

 

그리고, 주어진 과제의 마감기한 중 가장 긴 마감기한을 MaxDeadLine에 저장해주었다.

이 값은 해결할 과제를 저장할 배열을 효율적으로 resize하기 위해 구해주었다.

 

std::vector<int> HomeWorks(MaxDeadLine + 1,  0);

while (Queue.size() > 0)
{
    std::pair<int, int> CurHomeWork = Queue.top();
    Queue.pop();

    int CurIndex = CurHomeWork.second;

    while (CurIndex > 0)
    {
        if (HomeWorks[CurIndex] == 0)
        {
            HomeWorks[CurIndex] = CurHomeWork.first;
            break;
        }

        CurIndex--;
    }
}

 

HomeWork배열은 해결할 숙제를 저장할 배열이다. 해당 배열의 i번째 인덱스의 원소는 i일차에 해결할 과제의 점수이다.

0번 인덱스는 사용하지 않는다.

 

다음은 점수순으로 정렬된 우선순위 큐에서 가장 위의 원소를 꺼내주어, 해당 원소를 HomeWork배열에 등록해주었다.

마감일자에 해당하는 인덱스에 과제가 배정되어 있지 않다면, 해당 인덱스에 점수를 저장해주었고 만약 과제가 배정되어 있다면, 인덱스를 1씩 빼며 배정할 수 있는 자리가 있나 탐색해주었다.

 

이 과정을 우선순위 큐가 모두 빌 때까지 반복하였다.

int GradeSum = 0;

for (int i = 0; i < HomeWorks.size(); i++)
{
    GradeSum += HomeWorks[i];
}

std::cout << GradeSum;

return 0;

 

이후, 배정된 과제 배열의 점수를 모두 더해준 뒤 출력해주면 끝이다.

 

풀이 코드

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

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int main()
{
    Init();

    int NumOfHW = 0;
    std::cin >> NumOfHW;

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::less<std::pair<int, int>>> Queue;

    int MaxDeadLine = 0;

    for (int i = 0; i < NumOfHW; i++)
    {
        int DeadLine = 0;
        int Grade = 0;
        std::cin >> DeadLine >> Grade;

        Queue.push({ Grade, DeadLine });

        MaxDeadLine = std::max(DeadLine, MaxDeadLine);
    }

    std::vector<int> HomeWorks(MaxDeadLine + 1,  0);

    while (Queue.size() > 0)
    {
        std::pair<int, int> CurHomeWork = Queue.top();
        Queue.pop();

        int CurIndex = CurHomeWork.second;
        
        while (CurIndex > 0)
        {
            if (HomeWorks[CurIndex] == 0)
            {
                HomeWorks[CurIndex] = CurHomeWork.first;
                break;
            }

            CurIndex--;
        }
    }

    int GradeSum = 0;

    for (int i = 0; i < HomeWorks.size(); i++)
    {
        GradeSum += HomeWorks[i];
    }

    std::cout << GradeSum;

    return 0;
}