-
백준 1335번: 트럭큐(Queue) 2020. 2. 6. 16:53반응형
https://www.acmicpc.net/problem/13335
13335번: 트럭
문제 강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최
www.acmicpc.net
큐를 이용하면 쉽게 풀리는 문제
L -> 다리가 견딜수 있는 무게
W -> 다리의 길이
키워드 - queue
Source
#include <iostream> #include <sstream> #include <string> #include <algorithm> #include <functional> #include <vector> #include <list> #include <queue> #include <deque> #include <map> #include <set> #include <stack> #include <math.h> #include <memory.h> using namespace std; #define MAX_SIZE 100 #define INF 0x7fffffff #define CENDL "\n" #define ll long long #define c_reverse(s) reverse(s.begin(), s.end()) #define c_sort(s) sort(s.begin(), s.end()) #define print_vector(v) for(int i=0; i<v.size(); i++) cout << v[i]; int main() { cin.tie(0); std::ios::sync_with_stdio(false); int n, w, l; cin >> n >> w >> l; queue<int> q; int sum, count; sum = count = 0; while (n--) { int d; cin >> d; while (true) { if (q.empty()) { q.push(d); count++; sum += d; break; } else if (q.size() == w) { sum -= q.front(); q.pop(); } else { if (sum + d > l) { q.push(0); count++; } else { q.push(d); count++; sum += d; break; } } } } cout << count + w << CENDL; return 0; }
반응형'큐(Queue)' 카테고리의 다른 글
백준 1715번: 카드 정렬하기 (0) 2018.08.05 백준 10866번: 덱 (0) 2018.06.20 백준 10845번: 큐 (0) 2018.06.20 백준 1927번: 최소힙 (0) 2018.06.17 백준 11279번 : 최대 힙 (0) 2018.06.17