문제 개요 #

• Source: 백준 컵라면
• Difficulty: Gold 2
• Key Concept: 우선순위 큐, 그리디 알고리즘

접근 방법 #

이번 문제는 데드라인이 정해져있는 문제들을 선택하여 풀어서 컵라면의 수를 최대화하는 문제입니다.

먼저 각 문제들은 데드라인과 얻을 수 있는 컵라면의 수가 있음을 알 수 있습니다.

이렇게 각 문제별 데드라인이 있었다면 선택해야될 기준을 오늘 데드라인이 임박한 문제들 중에 컵라면을 가장 많이 얻도록 하였습니다. 따라서 해당 문제는 데드라인을 기준으로 정렬한 뒤 동일하다면 컵라면의 수를 기준으로 내림 차순으로 정렬되도록 하였습니다.

이후 오늘의 날짜를 기준으로 데드라인을 따라가면서 얻을 수 있는 컵라면의 수가 가장 큰 문제들을 선택해 나가면서 얻을 수 있는 최대의 컵라면을 구하려고 하였습니다.

시행착오 #

위의 로직은 문제에서 말한 데드라인을 제대로 이해하지 못한 풀이었습니다. 즉 해당 문제를 데드라인의 날짜가 되어야 풀고 있는데 사실 데드라인에 임박하지 못해도 먼저 풀 수 있습니다.

예를 들어 아래와 같은 입력이 들어왔다면 데드라인이 3일이지만 1일차, 2일차에도 모든 문제를 풀 수 있습니다. 따라서 해당 입력의 결과는 15가 되어야 하나 앞에서 시도한 로직의 경우 얻을 수 있는 컵라면의 수가 5밖에 되지 않습니다.

데드라인에 임박하기 전에도 오늘 풀 수 있는 문제라면 일단 모두 기록한 다음 최종단계에서 각 날짜 별로 최대값을 선택하도록 해야 합니다.

해결 방법 #

컵라면의 수를 최대화하기 위해 priority_queue¹를 사용하였습니다. priority_queue에 일단 문제를 넣고 해당 문제의 데드라인보다 많이 들어갔다면, 즉 문제의 단위 시간이 1이므로 단위시간의 합보다 데드라인이 작다면 해당 문제는 데드라인을 넘긴 문제가 됩니다.

이 때 priority_queue pop을 한다면 자동으로 컵라면의 value가 가장 낮은 문제가 제외됩니다. 또한 데드라인에 임박한 문제가 아니더라도 value를 우선적으로 확인하기 때문에 앞 서 설명한 문제들도 해결됩니다.

// 최종 해결 코드
#include <bits/stdc++.h>

using std::pair;
using std::priority_queue;
using std::vector;

int solution(vector<pair<int,int>> problems){
    int answer = 0;
    std::sort(problems.begin(), problems.end());

    priority_queue<int, vector<int>, std::greater<int>> pq;

    for (int i = 0; i < n; i++) {
        int d = problems[i].first;
        int v = problems[i].second;

        pq.emplace(v);

        if (pq.size() > d) {
            pq.pop();
        }
    }

    long long answer = 0;
    while (!pq.empty()) {
        answer += pq.top();
        pq.pop();
    }
    return answer;
}

알고리즘 설명 #

문제의 데드라인과 컵라면 수가 first와 second에 들어있는 problems를 데드라인을 기준으로 먼저 정렬합니다. 이 때 컵라면의 수는 자동으로 priority_queue에서 정렬이 되므로 할 필요는 없습니다.

이후 모든 문제들에 대해서 데드라인과 컵라면의 수를 할당 후 우선순위 큐에 컵라면의 수를 먼저 넣고, 이후 해당 데드라인이 단위 시간들의 총 합보다 작다면 즉 해당 문제의 데드라인이 이미 지났다면 가장 컵라면 수가 낮은 문제 하나를 버리고 다음 문제에 대해서 동일한 로직을 반복합니다.

아래는 로직을 도식화한 다이어그램입니다.

graph TD
    subgraph 초기 설정
        A["문제들을<br/>데드라인 기준으로 정렬"]
        B["비어있는<br/>최소 힙 우선순위 큐(PQ) 생성"]
    end

    subgraph "핵심 로직 반복 (각 문제에 대하여)"
        direction TB
        C["현재 문제<br/>(데드라인: D, 컵라면 수: R)"] --> D["컵라면 수(R)를<br/>PQ에 추가"];
        D --> E{"PQ의 크기가 데드라인(D)보다 큰가?"};
        E -- "True <br> 데드라인 초과!" --> F["PQ에서 가장<br/>컵라면 수가 적은 문제 제거"];
        F --> G((다음 문제로));
        E -- "False <br/>시간 여유 있음" --> G;
    end

    H([최종 계산])
    I["PQ에 남아있는<br/>모든 컵라면 수 합산"]

    A --> B;
    B --> C;
    G --> C;
    C -- 반복 종료 --> H;
    H --> I;

성능 분석 #

• Time Complexity: $O(N \log N) $
• Space Complexity: $O(N)$

핵심 정리 #

해당 로직은 PQ의 크기가 무엇을 의미하는지 고민하는 과정이 중요했습니다. 또한 우선순위를 바탕으로 pop이 되는 priority_queue의 특징을 이해하고 활용할 수 있는 능력이 필요합니다. 그리디 알고리즘을 바탕으로 우선순위 큐를 이용하여 조건에 맞지 않을 때 최악의 선택지를 버리는 문제로 바라보는 능력을 요하는 문제입니다.

참고자료 #