Programmers 라면공장(C++)

programmers : https://programmers.co.kr/learn/courses/30/lessons/42629#qna

코딩테스트 연습 - 라면공장

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.

해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.

현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요.

 

Level 2 <Heap> 라면공장 문제입니다.

 

이 문제 처음에는 정말 어렵더라구요..

어떻게 하면 밀가루를 최소한의 횟수로 공급받으면서 K 날짜가 될때까지 버틸 수 있을까

 

이 문제를 풀기 위해서 dfs로 재귀를 돌려보다가 DP까지 적용시켜서 시도해봤는데 모두 실패했습니다.

그러다가 문제가 heap 분류에 있었다는 것을 떠올렸고

대체 어떻게? heap으로 이 문제를 푸는거지 생각해봤는데

 

다시보니 되게 간단하더라구요.. 너무어렵게 생각했었습니다.

 

현재 날짜를 today라고 하면, 이 today가 될때 까지 사용한 밀가루가 있을테고 공급받은 밀가루도 있을 것입니다.

밀가루 양 상관없이 K날짜까지 버틸 수 있는 최소한의 공급횟수!

==> 오늘 날짜인 today까지를 기준으로 받을 수 있는 공급 밀가루를 최대한 많은 순서로 받으면 되는 것이였습니다.

 

즉 오늘날짜가 만약 4일이다.

=> 4일까지 공급받을 수 있는 밀가루를 heap에 저장해두시구요

heap중에서 가장 큰 밀가루 값을 꺼내서 이 밀가루 양만큼 최대한 버텨주면 되는겁니다.

만약 꺼낸 밀가루 양이 20이라면, 24일까지는 버틸 수 있는 얘기고 -> 4일~24일까지 오는 날짜에 받을 수 있는 밀가루를 또 heap에 저장 --> heap에서 가장 큰 값 꺼내기! --> 반복..

 

참고로 K 날짜가 되는 날 아침을 기준으로 하기때문에 K날짜인 아침날 stock가 0이 되어도 괜찮다는건

문제를 읽으셨다면 아실꺼라고 생각합니다.

이게 무슨뜻이냐.. K-1날짜까지만 버텨주면 된다. 라는 의미가 되겠네요

 

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

using namespace std;

int solution(int stock, vector<int> dates, vector<int> supplies, int k) {

    priority_queue<int, vector<int>, less<int> > q;

    int cnt = 0; // 공급받을 횟수!
    int s = 0; // 어떤 인덱스(공급날짜)부터 검색할 것인지를 위해
    int today = stock; // 오늘날짜는 0일부터 시작하기 때문에 stock를 더해서 시작해주면 되겠네요

    while (today < k) {
        // s(공급날짜 시작일의 인덱스)부터 today를 비교해가며 공급받을 수 있는 날을 heap에 저장
        for (int i = s; i<dates.size(); i++, s++) { // s날짜는 조건에만 부합하다면 항상 +1씩 증가하겠네요!
            if (dates[i] <= today) q.push(supplies[i]);
            else break;
        }
        cnt++;
        today += q.top(); // 버틸수있는 날짜를 더해줍니다
        q.pop();
    }

    return cnt;
}