백준 20055번: 컨베이어 벨트 위의 로봇 (C++)

1. 문제 링크

20055번: 컨베이어 벨트 위의 로봇

2. 소스코드

#include <iostream>
#include <deque>
using namespace std;
deque<int> r1; //컨베이어 벨트의 윗줄-로봇 위치 저장
deque<int> a; //내구도
int dx = 0;
int main() {
	int n, k, stage = 1, cnt = 0, temp;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		r1.push_back(0);
	}
	for (int i = 0; i < 2 * n; i++) {
		cin >> temp;
		a.push_back(temp);
	}
	while (1) {
		//한 칸 회전
		r1.pop_back();
		r1.push_front(0);
		if (r1.back() == 1)r1[n - 1] = 0;
		temp = a.back();
		a.pop_back();
		a.push_front(temp);
		//로봇 이동
		for (int i = n - 2; i > 0; i--) {
			if (r1[i] == 1) {//로봇이 있는 칸
				if (a[i + 1] > 0 && r1[i + 1] == 0) {
					a[i + 1]--;
					if (a[i + 1] == 0)cnt++;
					if (i == n - 2) {
						r1[i] = 0;
					}
					else {
						r1[i + 1] = 1;
						r1[i] = 0;
					}
				}
			}
		}
		//로봇 올리기
		if (a[0] > 0) {
			r1[0] = 1;
			a[0]--;
			if (a[0] == 0)cnt++;
		}
		if (cnt >= k)break;
		stage++;
	}
	cout << stage;
}

3. 노트

3-1.deque를 이용한 회전 구현

컨베이어 벨트를 하나의 연속적인 자료구조로 본다면, 벨트가 한 칸 이동하는 것은 맨 뒤 원소를 꺼내 맨 앞에 붙이는 과정을 반복하는 것으로 볼 수 있다. 이 때문에 queue를 이용할까 했는데, 벨트가 시계방향으로 회전하므로, 즉 맨 앞 원소를 맨 뒤에 붙일 수 있는 큐와 반대로 맨 뒤 원소를 맨 앞에 붙여야 하므로 덱을 이용했다.
이 때 내구도를 저장하는 덱의 길이는 2*n인데, 로봇의 위치를 저장하는 덱의 길이는 n으로 처리하였다. 왜냐 하면, 로봇은 컨베이어 벨트의 윗줄에서만 움직이기 때문이다.

3-2.C++ STL의 deque에서는 인덱스로 deque의 n번째 원소를 접근할 수 있음

로봇을 새로 올릴 때, 로봇이 이동할 때 내구도를 감소시켜야 하는데, C++의 STL에서는 인덱스로 n번째 원소에 접근하여 수정할 수 있다. 이를 이용하여 쉽게 구현할 수 있었다.