다리를 지나는 트럭
생각을 전환하면 쉽게 풀리는 문제 <- 이게 어렵다
순서대로 나가야 하기 때문에 queue를 활용
queue에는 무게, 시간 을 쌍으로 저장해준다.
이때, 시간을 시작 시간으로 하게 된다면 1초마다 queue에 있는 모든 시간을 다 늘려줘야 한다.
- 불가능
따라서 queue에 원래 끝나야 하는 시간을 넣어줘서 queue의 앞에 것만 체크해 주면서 끝내자.
남은 트럭 = 벡터
다리 = queue 로 생각하자
생각해야 할 조건
1
2
3
4
5
6
7
1. 다리에도 없고, 남은 트럭도 없는 경우
2. 다리에만 있는 경우 (벡터에 값이 없을 때)
3. 남은 트럭이 있는 경우
A. 다리에 있는 경우
- 시간 다 된 것이 있으면 빼줘야 한다.
B. 다리의 무게가 다음 트럭을 버틸 수 있다면 넣기
- 버티지 못한다면 맨 앞의 것을 빼기
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
48
49
50
51
#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> p;
int solution(int len, int w, vector<int> t) {
queue<p> q;
int answer = 1;
int siz = t.size();
int i = 0;
while(1){
int nowTime = answer;
if(!q.size() && i == siz){ // 다리에도 없고, 남은 트럭도 없는 경우
break;
}
if(i == siz){ // 다리에만 있는 경우
int tempTime = q.front().first;
answer = tempTime;
q.pop();
}
else // 남은 트럭이 있는 경우
{
if(q.size()) // 다리에 있는 경우
{
int tempTime = q.front().first;
int tempW = q.front().second;
if(nowTime == tempTime){ // 시간 다 된거 빼주기
q.pop();
w += tempW;
}
}
if(t[i]<=w){ // 버틸 수 있다면 넣기
w -= t[i];
p temp = make_pair(nowTime + len,t[i]);
q.push(temp);
i++;
answer++;
}
else{ // 그 time에 버틸 수 없다면 빼기
int tempTime = q.front().first;
answer = tempTime;
w += q.front().second;
q.pop();
}
}
}
return answer;
}
