- 문제
//시간제한: 1초, 메모리 제한: 512MB
- 입력
입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.
- 출력
출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.
#include<iostream>
#include<queue>
#include<deque>
using namespace std;
queue<int> q;
deque<pair<int, int>> bridge;
int n, w, l, weight, sum, ans;
int main() {
cin >> n >> w >> l;
for (int i = 0; i < n; i++) {
cin >> weight;
q.push(weight);
}
while (!q.empty() || !bridge.empty()) {
if (!bridge.empty()) { //다리 위의 트럭들을 한칸식 전진
for (int i = 0; i < bridge.size(); i++) {
bridge[i].second++;
}
}
for (int i = 0; i < bridge.size(); i++) { //한칸씩 트럭을 전진 시켰을 때 다리를 다 건넌 트럭이 있는지 확인
if (bridge[i].second > w) { //트럭이 다리를 건넜다면
sum -= bridge[i].first;
bridge.pop_front();
}
}
if (!q.empty() && q.front() + sum <= l && bridge.size() < w) { //다리 위에 자리가 있고 트럭이 다리 위에 올라갔을 때 최대하중을 넘지 않는 다면, 트럭을 다리 위로 올림
bridge.push_back({q.front(), 1});
sum += q.front();
q.pop();
}
ans++;
}
cout << ans;
}풀이
queue와 deque를 이용하여 문제를 해결했다.
트럭의 줄을 queue에 입력받았고, 다리 위의 트럭들을 deque bridge를 선언하여 관리했다.
deque를 사용한 이유는 순환할 수 있고 삽입삭제가 빠른 자료구조이기 때문에 선택했다. pair로 선언하여 first에는 트럭의 무게, second에는 얼만큼 전진했는지 넣어주었다.
현재 다리 위의 트럭 무게 합을 담아서, bridge에 push,pop할 때마다 갱신해주었다.
모든 트럭이 다리를 다 건널 때 까지 반복문을 돌며
다리 위에 트럭이 있다면 second++로 한칸씩 전진시켜주고,
한칸씩 전진했을 때 다리 길이보다 커진 트럭을 pop해주었다.
다리 위에 자리가 있고, q.front()의 트럭 무게를 sum에 더했을 때 최대하중을 넘지 않으면 다리 위에 push해주었다.
ans를 카운팅 하며 총 걸린 시간을 계산한 후 마지막에 ans를 출력해주었다.
처음 문제를 풀 때는 위의 풀이처럼 한칸한칸 다 계산 해주는 것이 아니라 ans에 w를 바로 더해주고, 앞 트럭의 바로 붙어서 따라가는 트럭은 ans++하는 식으로 구현했더니 여러 예외들을 처리해 주어야하고 코드가 너무 복잡해져서 한번 싹 갈아 엎었다. 그랬더니 얼마 걸리지 않아 바로 문제를 해결할 수 있었다.
처음 생각한 알고리즘이 별로고, 이 방법으로 해결하기 어렵다고 느껴지면 과감하게 코드를 새로 짜는 것도 하나의 방법이 될 수 있다고 생각하게 되었다.
KIM DONGWAN