프로그래머스 - 라면공장

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

 

문제 설명

밀가루 공장이 고장나서 라면 공장이 밀가루를 못받게 되어 해외 공장에서 밀가루를 수입해야 하는 상황이다.
해외 공장에서 밀가루 공급일과 수량을 알려주었다.
운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶다.

라면 공장이 버틸 수 있는 최소한의 수입 횟수를 리턴하자.

 

제한 사항

• 비축분은 오늘부터 사용한다.
• 2 <= 비축분, 공급 재개일자 <= 100,000
• 1 <= 공급 날짜 <= 공급 재개일자
• 1 <= 밀가루 공급량 <= 1,000
• 1 <= 밀가루 공급이 가능한 날 <= 20,000
• 날짜는 오름차순으로 정렬되어 있다.
• 밀가루는 새벽에 도착한다.
  • 전 날에 다 떨어져도, 당일에 수입할 수 있으면 된다.
• 공급이 불가능한 경우는 주어지지 않는다.

 

1. heap 사용하기 - O(NlogN)

 

제한 사항이 상당히 많은 문제다. 문제를 이해하는 데 걸리는 시간이 더 오래 걸릴수도 있다.
간단하게 생각하면 다음과 같다.

 

• 현재까지의 비축분이 i라면, 늦어도 i일에는 수입을 해야한다.
  • ex) 지금까지의 비축분이 4라면, 늦어도 4일 새벽에는 수입을 해야한다
• 공급 재개일자부터 다시 공급이 되기 때문에, 공급 재개일자 전날 까지의 밀가루만 확보하면 된다.
  • 공급 재개일자 전날 까지 필요한 밀가루는 공급 재개일자의 수와 같다.
  • 공급 재개일자가 30일이라면, 비축분 포함 최소 30톤을 확보하면 된다.

  한마디로, 밀가루를 총 공급 재개일자수 만큼 확보하는데 필요한 최소 공급일수를 묻는 문제이다.
문제에서 주어진 예시를 보면서 생각해보자.

 

---

• 현재 비축분 : 4
• 공급 재개일자 : 30

일자	4	10	15
수량	20	5	10

---

 

처음의 비축분은 4톤이다. 따라서 늦어도 4일 새벽에는 수입을 해야 한다.
이 때, 수입할 수 있는 날짜는 언제가 있을까?
4일 하나 뿐이다.
10일과 15일은 너무 늦다. 따라서 4일에는 필수적으로 수입해야 한다.
그러면 총 비축분은 4 + 20 = 24 톤이다.

그러면 이제 늦어도 언제까지는 수입을 해야 할까?
24톤이므로 늦어도 24일 새벽에는 수입을 해야 한다.
이 때, 수입할 수 있는 날짜는 언제가 있을까?
10일과 15일 두 경우가 있다.
10일에 수입을 하면 5톤이 추가되고, 15일에 수입을 하면 10톤이 추가된다.

5톤을 수입하면 총 비축분은 29톤이 되고, 10톤을 수입하면 총 비축분은 34톤이 된다.
5톤을 수입하면 버틸 때 까지 1톤이 부족하게 되므로, 15일자를 추가로 수입해야 한다.
하지만 10톤을 수입하게 되면 4톤의 여유가 생긴다. 추가로 수입할 필요가 없어진다.

따라서, 4일과 15일에 밀가루를 수입하면 2번만 수입하면 되므로 2가 정답이 된다.

 

그렇다면 이 문제를 어떻게 풀면 좋을까?

현재 비축된 밀가루의 양을 토대로, 언제까지 버틸 수 있는지 확인한다.
버틸 수 있는 날짜 중, 가장 많은 양의 밀가루를 수입할 수 있는 날짜를 골라 수입을 하면, 최소한의 수입으로 필요한 밀가루를 보충할 수 있을 것이다.

버틸 수 있는 날짜 중에서 가장 많은 양의 밀가루는 어떻게 구할까?
여기에서 등장하는 것이 힙이다.
힙을 이용하여 수입할 수 있는 밀가루의 최댓값을 가지고 있을 수 있다.

문제의 예시를 힙을 이용하여 흐름을 알아보자.

---

현재 비축량은 4다. 버틸 수 있는 날짜는 4까지다.
따라서 힙에 4일에 수입할 수 있는 밀가루, 20을 집어넣는다.

현재 힙의 최댓값은 20이다. 20을 비축량에 더해준 뒤, 힙에서 20을 빼 주자.

현재 비축량은 24이다. 버틸 수 있는 날짜가 10일과 15일이 추가되었다.
이제 10일에 수입할 수 있는 밀가루 5와 15일에 수입할 수 있는 밀가루 10을 힙에 넣어주자.

현재 힙의 최댓값은 10이다. 10을 비축량에 더해준 뒤, 힙에서 10을 빼 주자. 그러면 힙에 5가 남는다.

현재 비축량은 34이다. 이 이상으로는 수입하지 않아도 공급 재개일자까지 버틸 수 있으므로 2회 수입으로 답을 리턴한다.

---

 

그러면 이 과정을 코드로 작성해보자.

 

#include <vector>
#include <queue>

using namespace std;

int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
    int answer = 0, idx = 0, len = static_cast<int>(dates.size());
    priority_queue<int> pq;
    
    while (stock < k)
    {
        while ((idx < len) && (stock >= dates[idx]))
            pq.push(supplies[idx++]);
        
        stock += pq.top();  pq.pop();
        ++answer;
    }
    
    return answer;
}

 

문제를 이해하는데 시간은 오래 걸릴 수 있으나,
핵심을 파악하면 수월하게 풀 수 있는 문제다.
복잡해 보이는 문제라도 차분하게 생각할 수 있는 힘을 기르자.