BOJ 13335 - 트럭

13335번: 트럭 (acmicpc.net)

13335번: 트럭

 

접근 방법

순서 변경이 없고, 선입선출이라는 것이기 때문에 큐를 이용하면 좋겠다고 생각했다.

 

1. 만약 다리 하중을 버틸 수 있으면, 큐에 트럭을 넣는다. 이때, 현재 다리 위에 올라간 트럭의 총 무게(현재 무게)에 해당 트럭의 무게를 더한다.

2. 그렇지 않으면, 큐에 공백을 넣는다.

3. q.front()가 트럭일 땐, 트럭이 다리를 다 건넌겄이므로 현재 무게에서 트럭 무게만큼 빼준다.

 

코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>

#define MAX 100002
#define INF 100002

using namespace std;

int n,w,l;
int truckWeight[1001];
queue<int> q;
int k; // 회전 횟수

int curWight = 0;
vector<int> passed;



int main() {
	cin.tie(NULL); ios_base::sync_with_stdio(false);

	cin >> n >> w >> l;
	for (int i = 0; i < n; i++) {
		cin >> truckWeight[i];
	}
	
	for (int i = 0; i < w; i++) {
		q.push(-1);
	}

	/*q.push(0);
	curWight = truckWeight[0];*/

	int cnt = 0;
	int idx = 0;
	while (!q.empty()) {

		cnt++;

		int front = q.front();
		if (front != -1) {
			//cout << "cnt: " << cnt << endl;
			curWight -= truckWeight[front];
		}
		q.pop();

		if (idx < n) {
			// 다리 하중 이하이면, 트럭 넣기
			if (curWight + truckWeight[idx] <= l) {
				q.push(idx);

				curWight += truckWeight[idx];
				idx++;
			}
			else {
				//cout << "공백 넣기" << endl;
				q.push(-1);
			}
		}
		
	}

	cout << cnt;
}