라면 공장
-
날이 갈 때 마다 모든 supply를 검사해 줄 수 없다
-
최소로 공급 받고 싶다 = 한 번 받을 때 최대로 받자
-
함부로 지원을 안 받으면 아예 최종 목적지 까지 못 갈 수도 있다.
-
자신의 stock에 있는 밀가루로 버틸 수 있는 날까지 탐색을 해준다. (dates는 오름차순)
-
그 때, supplies 에 있는 값 들을 priority queue에 넣어줘서 가장 큰 것으로 충전을 한다.
-
pq에는 값과, date를 넣어주자.
왜? Date를 바꿔줘야 하니까
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <string>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> p;
int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
int answer = 0;
int date = 0;
priority_queue<p> pq;
for (int i = 0; i < dates.size(); i++) {
if ((date + stock) < k) {
if ((date + stock) >= dates[i]) { // 거기까지 갈 수 있다는 뜻
p temp = make_pair(supplies[i], dates[i]);
pq.push(temp);
}
else { // 무조건 갈 수 있으니 pq에는 데이터가 있다.
i--;
int tempSup = pq.top().first;
int tempDate = pq.top().second;
stock += tempSup;
if(date < tempDate){
stock -= (tempDate - date);
date = tempDate;
}
pq.pop();
answer++;
}
}
else {
return answer;
}
}
while ((date + stock) < k) {
int tempSup = pq.top().first;
int tempDate = pq.top().second;
stock += tempSup;
if(date < tempDate){
stock -= (tempDate - date);
date = tempDate;
}
pq.pop();
answer++;
}
return answer;
}
