[고득점Kit][힙] 라면 공장 ⭐⭐

[힙] 라면 공장

난이도 ⭐⭐

문제

풀이

어떻게 풀어야할지 아예 모르겠어서.. 30분만 딱 고민해본 후 다른 분들의 풀이를 참고했던 문제다. 근데 다른 분들의 풀이를 보자마자 생각보다 간단한 풀이였다는 것을 알게 되서 좀 더 고민해볼걸 그랬나 싶었다. 😥

밀가루를 최소한으로 공급받으려면 재고가 0이 될 때까지 최대한 쓰고난 후 최대로 공급되는 양으로 받아야 한다.

• 👉 즉, 밀가루 양 supplies를 Max Heap 우선순위 큐에서 관리해야 한다는 얘기
  • 💡 밀가루 받을 수 있는 날마다 우선 순위 큐에 받아 놓기
    • answer는 증가 X
  • 💡 stock이 0 이 될 때마다 우선 순위 큐에 받아 두었던 밀가루들 중 가장 큰 양을 pop 하여 stock에 더해준다.
    • answer는 증가
• day의 범위는 0 ~ k-1 이며 day가 1씩 늘어날 때마다 stcok은 1 씩 줄어든다.
  • 하루에 1톤씩 쓰기 때문

#include <string>
#include <vector>
#include <queue>

using namespace std;

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

    int index = 0;
    for(int day = 0; day < k; day++)
    {
        if (day == dates[index])
        {
            pq.push(supplies[index]);
            index++;
        }
        
        if (stock == 0)
        {
            stock += pq.top();
            pq.pop();
            answer++;
        }
        
        stock--;
    }
    
    return answer;
}

• 우선순위큐 pq 👉 밀가루 공급 날마다 받아 둘 Max Heap
• index 👉 dates, supplies를 순회할 인덱스
• day를 하루하루 k-1 까지 증가시키는 과정
  • if (day == dates[index])
    • 밀가루를 공급받을 수 있는 날이 되면
      • 우선순위큐에 일단 해당 밀가루 양을 미리 넣어둔다.
      • index 증가
  • if (stock == 0)
    • 재고가 떨어질때마다 우선순위큐에 받아두었던 밀가루를 pop 한다.
      • 👉 Max Heap이므로 밀가루 최대 공급량이 pop됨
    • stock에 이를 더해준다.
    • stock에 반영했으니 우선순위 큐에서 빼준 후
    • answer 증가

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기