백준 13335번 트럭(c++)

13335번: 트럭

문제 분석

트럭 문제를 읽고, 트럭이 순차적으로 다리에 오르는 것에 초점을 맞추고 알고리즘을 생각했다.

이에 while문에서 '1초가 지날 때마다 다리에 오르는 트럭'을 중점으로 뒀다. 

그러면 1초가 지날 때마다 생각해야 하는 경우는 무엇이 존재할까?

 

1. 1초가 지난다면, 다리 위의 트럭이 한 칸씩 움직여야 한다.
   다리 끝의 트럭은 1초가 지난다면 다리에서 내리게 되고, 다리가 견디는 현재 하중에서 빠져야 한다.
   
   
2. 트럭이 다리에 오르기 위해서는 다리의 최대 하중을 넘기지 않아야 한다.
   -> (현재 다리 위의 무게 + 새로 들어올 트럭의 무게)가 다리의 최대 하중을 넘는가?

---

문제 풀이

먼저 while문의 처음에 단위시간이 1초씩 증가하도록 하여, 시간이 흐르는 반복문을 만든다.

문장 처음에 시간이 지남으로, 1초가 지났을 때 아래 동작을 수행한다고 생각하면 좋다.

 

위 1번. 현재 다리에 있는 트럭은 1초 전의 트럭 위치이므로, 이들을 이동시키도록 한다.

 

1) 다리는 0으로 초기화시켰기에, index의 처음 원소가 0이 아니라면 트럭이 있었던 것이다.

-> 그렇다면 트럭은 1초가 지나면 하차하고, 현재 하중에서 빠지게 된다.

 

2) 그 뒤의 index부터는 트럭이 한칸씩 앞으로 이동하도록 한다.

 

위 2번. 단위시간 1초마다 트럭이 내림과 동시에, 최대하중을 넘지 않는다면 트럭이 다리에 올라야 한다.

단! 최대 하중을 넘지 않는다면!

(문제 : 이 떄, 트럭이 다리에 걸쳐있는 것은 무게를 계산하지 않는다.)

 

1) (현재 다리 위의 무게 + 새로 들어올 트럭의 무게) >= 최대 하중

-> 트럭이 다리에 오를 수 있는 상태이다. 현재 하중에 트럭 무게를 더하고, 다리 배열의 끝에 트럭을 추가한다.

 

2) (현재 다리 위의 무게 + 새로 들어올 트럭의 무게) < 최대 하중

-> 트럭이 오를 수 없는 상태이다. 이번 시간에는 오를 수 없기에 PASS.

C++ 풀이

#include <iostream>
#include <vector>
#include <queue>

using namespace std;


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, w, L;
	cin >> n >> w >> L;

	vector<int> t(n, 0);

	for (int i = 0; i < n; i++)
		cin >> t[i];

	queue<int> truck; // 다리에 오르지 못한 트럭
	for (int i = 0; i < n; i++)
		truck.push(t[i]);
	// ----------------입력 받는 과정--------------------
    
	int now = 0, T = 0; // now : 현재 다리 위의 무게, T : 단위 시간
	vector<int> ladder(w, 0); // ladder : 다리 위의 트럭
	bool flag = true; // 다리 위에 트럭이 있으면 true, 없으면 false

	while (flag) { // 1초마다 트럭이 다리에 있는 조건을 확인함.
		T++;
		flag = false;
        
		if (ladder[0] != 0) {
			now -= ladder[0];
			ladder[0] = 0;
		} // 다리를 나간 트럭은 없애줌. 현재 무게에서 차감.
		
		for (int i = 1; i < w; i++) {
			if (ladder[i] != 0) {
				int temp = ladder[i];
				ladder[i] = ladder[i - 1];
				ladder[i - 1] = temp;
			}
		} // 트럭을 다리에서 한칸씩 이동시켜줌.
        
		if (!truck.empty()) { // = 다리에 오르지 못한 트럭이 있다면
			if (now + truck.front() <= L) {
				now += truck.front();
				ladder[w - 1] = truck.front();
				truck.pop();
			}
		}
        // (현재 무게 + 들어올 트럭)이 최대 하중L 보다 작다면 진입 가능.
        // 현재 무게에 들어올 트럭 더하기. 다리 끝에 트럭 추가.
        // 트럭이 다리에 올랐기에 truck에서 첫 요소 삭제.
		
		for (int i = 0; i < w; i++) {
			if (ladder[i] != 0)
				flag = true;
		}
        // 만약 다리에 트럭이 존재한다면 아직 while문 종료되면 안됨.
	}

	cout << T;

	return 0;
}

코드 리뷰는 언제나 환영입니다!