문제
라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.
해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.
현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요.
dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.
제한사항
- stock에 있는 밀가루는 오늘(0일 이후)부터 사용됩니다.
- stock과 k는 2 이상 100,000 이하입니다.
- dates의 각 원소는 1 이상 k 이하입니다.
- supplies의 각 원소는 1 이상 1,000 이하입니다.
- dates와 supplies의 길이는 1 이상 20,000 이하입니다.
- k일 째에는 밀가루가 충분히 공급되기 때문에 k-1일에 사용할 수량까지만 확보하면 됩니다.
- dates에 들어있는 날짜는 오름차순 정렬되어 있습니다.
- dates에 들어있는 날짜에 공급되는 밀가루는 작업 시작 전 새벽에 공급되는 것을 기준으로 합니다. 예를 들어 9일째에 밀가루가 바닥나더라도, 10일째에 공급받으면 10일째에는 공장을 운영할 수 있습니다.
- 밀가루가 바닥나는 경우는 주어지지 않습니다.
입출력 예
| stock | dates | supplies | k | result |
| 4 | [4,10,15] | [20,5,10] | 30 | 2 |
입출력 예 설명
- 현재 밀가루가 4톤 남아 있기 때문에 오늘과 1일 후~3일 후까지 사용하고 나면 모든 밀가루를 다 사용합니다. 따라서 4일 후에는 반드시 밀가루를 공급받아야 합니다.
- 4일째 공급받고 나면 15일 이후 아침에는 9톤의 밀가루가 남아있게 되고, 이때 10톤을 더 공급받으면 19톤이 남아있게 됩니다. 15일 이후부터 29일 이후까지 필요한 밀가루는 15톤이므로 더 이상의 공급은 필요 없습니다.
- 따라서 총 2회의 밀가루를 공급받으면 됩니다.
풀이
왜 나는 문제 이해만 제대로 하는데 이렇게 오랜 시간이 걸리는지 모르겠다. 우선 문제를 잘못 이해해서 무조건 supplies를 순서대로 지급받는 식으로 코드를 짰더니 ㅋㅋㅋㅋㅋ 정확성에서 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;
int Dday = k-1;
priority_queue<int, vector<int>, less<int>> q;
for(auto& i : supplies) {
q.push(i);
}
if(stock>=k) return answer;
while(Dday>1){
if( (Dday-1) <=stock) break;
if(stock==0) {
stock+=q.top();
q.pop(); answer++;
}
stock--; Dday--;
}
return answer;
}
왜 이렇게 나왔나 하고 고민해보니까, 생각해보니 저 코드에는 dates와는 관계없이 모든 supplies를 우선순위 큐에 넣고 있었다. 즉, dates중 공급을 받을 수 있는 날짜의 supplies만 우선순위 큐에 넣는 코드가 빠져있던 것이다. ㅠㅠ 이걸 놓쳐서 계속 애꿎은 조건문만 수정하면서 헤맸다.
그래서 dates중 공급을 받을 수 있는 날짜를 어떻게 계산하는가 고민해보니 Dday로 접근할 게 아니라 현재 날짜(day)로 접근을 하는게 맞겠다 싶어 코드를 전면 수정했다. day가 지남에 따라 dates에서 공급받을 수 있는 항목이 생기니까 말이다. 먼저 세워놓았던 Dday의 개념은 for문의 조건에 넣어두었다.
최종 코드 C++
#include <string>
#include <vector>
#include <queue>
using namespace std;
int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
int answer = 0;
int index = 0;
priority_queue<int, vector<int>, less<int>> q;
for(int day = 0; day < k ; day++){
if(dates[index] == day) {
q.push(supplies[index]);
index++;
}
if(stock==0){
stock+=q.top();
q.pop();
answer++;
}
stock--;
}
return answer;
}
최종 풀이
1. 새로운 밀가루를 지급받는 날짜 k까지 날마다 stock은 감소, 현재 날짜 day는 증가
2. day가 증가함에 따라 새롭게 지급받을 수 있는 dates가 열림. 이 dates[index]에 따라 supplies[index]를 우선순위 큐에 넣어줌
3. stock==0이 되면 우선순위 큐에서 가장 큰 값(top)을 가져오고, 해당 값을 큐에서 제거. answer 증가
위와 같은 코드로 진행을 하면... 참 이상적일텐데 아예 아무것도 안 보고 해보자! 하면서 무한 삽질을 시작했더니 참 한심한(...) 접근을 많이 했다. 알고리즘 문제를 처음 풀어보면 다 이러는 걸까 ㅠㅠ 다들 되게 척척 잘 푸는 것 같아서 약간 기가 죽는다... ㅠㅠ 매일하다보면 늘겠지...? 파이팅이다
'Algorithm > BOJ' 카테고리의 다른 글
| [백준] 11724 : 연결 요소의 개수 (0) | 2020.07.31 |
|---|---|
| [백준] 1966. 프린터 큐 (0) | 2020.05.21 |
| [프로그래머스] 정렬 문제풀이 2 - K번째 수 (0) | 2020.01.19 |
| [프로그래머스] 정렬 문제풀이 1 - 가장 큰 수 (0) | 2020.01.19 |
| [프로그래머스] 힙 문제풀이 1 - 더 맵게 (0) | 2020.01.18 |
