프로그래머스 42629 - 라면공장 (c++)

프로그래머스 42629 - 라면공장

문제 링크

생각 및 접근

사족

• 나는 이런 문제에 약한 것 같다. 날짜와 데이터가 섞여서 최적의 결과를 나타내는 문제들. 연습을 좀 해야겠다.

본론

• dates와 supplies를 묶어서 관리하기 위해 새로운 구조체 Data를 하나 선언한다.

    struct Data{
        int date;
        int supply;
        Data(int a, int b): date(a), supply(b) {}
    };

• 밀가루를 공급받기 위해 판단의 기준이 되는 우선순위 큐 pq 하나와, 밀가루를 공급받기 위한 날짜의 후보를 넣어두는 큐 q 하나를 선언한다.

  • 우선순위 큐

      priority_queue<Data, vector<Data>, cmp> pq;

  • 큐

      queue<Data> q;
      for(int i = 0; i < dates.size(); i++)
          q.push(Data(dates[i], supplies[i]));

• 후보들은 q에서 대기하고 있다가, pq에 넣어질 수 있는 조건이 충족되면 그때서야 pq에 넣어진다.

  • 조건

    • 내가 가지고 있는 밀가루 양보다 q.front().date가 작아야 한다.

    • why : 공장의 운영이 끊기면 안된다. 밀가루 양 current가 current일까지 공장이 운영될 수 있는 날이고, 밀가루는 미리 받아놓거나 (current > q.front().date인 경우) 밀가루가 떨어진 바로 다음날 새벽 (current = q.front().date인 경우) 에 받을 수 있기 때문에, 다음과 같은 식이 성립될 때 pq에 넣을 수 있다.

        current >= q.front().date

• pq에 넣어진 것들은 supply가 가장 큰 순서대로 나열된다. 이는 밀가루를 greedy하게 골라 다른 날짜에서 밀가루를 또 받는 일을 방지한다.

    struct cmp{
        bool operator()(Data a, Data b){
            return a.supply < b.supply;
        }
    };

• pq의 top에 있는 것이 공장이 받을 밀가루가 되므로, current += pq.top().supply;

코드

#include <bits/stdc++.h>
using namespace std;

struct Data{
    int date;
    int supply;
    Data(int a, int b): date(a), supply(b) {}
};

struct cmp{
    bool operator()(Data a, Data b){
        return a.supply < b.supply;
    }
};

int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
    int answer = 0;
    int current = stock;

    priority_queue<Data, vector<Data>, cmp> pq;
    queue<Data> q;

    for(int i = 0; i < dates.size(); i++)
        q.push(Data(dates[i], supplies[i]));

    while(current < k){
        while(!q.empty() && current >= q.front().date){
            pq.push(q.front());
            q.pop();
        }

        current += pq.top().supply;
        pq.pop();
        answer++;
    }

    return answer;
}

채점 결과