[BOJ] 13904번 | 과제 (C++)

🔗문제 보러가기

13904번: 과제

 

👨‍💻풀이 과정

 

1. 과제 마감일을 기준으로 오름차순 정렬을 하되, 마감일이 같다면 점수가 높은 순으로 정렬해줍니다.
2. 경과된 날짜 변수를 0으로 세팅하고, 주어진 과제들을 순회합니다.
3. 기간 내에 가능한 숙제라면, 과제를 진행합니다.  (경과된 날짜 변수 + 1)
4. 마감일이 지났고 이미 완료한 과제들 중에 가장 낮은 점수보다 점수를 적게 준다면, 다음 과제를 확인합니다.
   • 이미 완료한 과제들이 항상 점수를 기준으로 오름차순 정렬이 되어 있도록, 우선순위 큐를 사용합니다.
   • 마지막 과제까지 확인을 했는데도 이 조건을 벗어나지 못한다면, 완료한 과제들의 점수를 합산하고 출력합니다.
   • 이 조건을 벗어나는 과제를 찾았다면, 탐색을 종료합니다.
     • 찾아낸 과제가 5번 조건에 만족하지 않는다면, 수행해야 하는 과제라는 뜻이므로 해당 과제를 수행합니다. (경과된 날짜 변수 + 1)
5. 마감일이 지난 숙제이며, 이미 완료한 과제들 중에 가장 낮은 점수보다 점수를 많이 준다면, 점수가 가장 낮은 완료한 과제를 빼고 해당 과제를 완료합니다.
   • 이 때는 이전에 했던 과제 대신 현재 과제를 한 것이므로, 경과된 날짜 변수가 증가하지 않습니다.
6. 모든 과제를 다 탐색했다면, 완료한 과제들의 점수를 합산하여 출력합니다.

 

✏️소스 코드 및 결과

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

using namespace std;
using Assignment = pair<int, int>;  // <남은 일 수, 점수>
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

int main()
{
    // 1. 입력 받기
    FAST_IO
    int N, remainedDay, point;
    cin >> N;
    
    vector<Assignment> assignments(N);
    for (int i = 0; i < N; i++)
    {
        cin >> remainedDay >> point;
        assignments[i] = make_pair(remainedDay, point);
    }

    // 2. 남은 날짜를 기준으로 오름차순, 남은 날짜가 같다면 점수가 높은 순으로 정렬
    sort(assignments.begin(), assignments.end(), [](const Assignment& a1, const Assignment& a2) {
        if (a1.first == a2.first)
            return a1.second > a2.second;
        return a1.first < a2.first;
    });

    // 3. 숙제 선정하기
    priority_queue<int, vector<int>, greater<int>> completedAssignments;
    int elapsedDay = 0, index = 0;

    while (index < N)
    {
        remainedDay = assignments[index].first;
        point = assignments[index].second;

        // 1) 기간 내에 가능한 숙제라면, 일단 클리어
        if (completedAssignments.empty() or elapsedDay < remainedDay)
        {
            completedAssignments.push(point);
            elapsedDay++;
            index++;
            continue;
        }
        
        // 2) 기간이 지난 숙제가 클리어 했던 숙제들 중에 가장 낮은 점수보다 점수가 낮다면, 다음 숙제를 확인
        while (index < N and remainedDay <= elapsedDay and point <= completedAssignments.top())
        {
            index++;
            remainedDay = assignments[index].first;
            point = assignments[index].second;
        }

        if (index >= N)
            break;

        // 3) 기간이 지난 숙제가 클리어 했던 숙제들 중에 가장 낮은 점수보다 점수가 높다면, 클리어 한 숙제는 버리고 해당 숙제를 클리어
        if (remainedDay <= elapsedDay and completedAssignments.top() < point)
        {
            completedAssignments.pop();
            completedAssignments.push(point);
            index++;
            continue;
        }

        // 4) 2)번에서 찾은 다음 과제이므로, 수행
        completedAssignments.push(point);
        elapsedDay++;
        index++;
    }

    // 4. 클리어 한 숙제들 점수 계산 후, 출력
    int totalPoint = 0;
    while (!completedAssignments.empty())
    {
        totalPoint += completedAssignments.top();
        completedAssignments.pop();
    }

    cout << totalPoint;
    return 0;
}