[백준 20055] 컨베이어 벨트 위의 로봇

문제

www.acmicpc.net/problem/20055

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

 

문제 풀이

간단한 구현 문제이지만 신경 써야 할 부분이 몇 가지가 있었습니다.

 

 1. 로봇이 내리는 경우는 벨트가 한 칸 회전해서 N번칸에 도착하거나 N-1번 칸의 로봇이 이동하여 N번칸에 도착하였을 때 총 두 가지뿐입니다.  

 

 2. 조금만 생각해보면 항상 로봇이 타는 번호가 1번이며 먼저 탄 로봇이 먼저 내리고 내리는 칸이 N번 칸이므로 로봇이 (N+1) ~ 2*N번 칸인 컨베이너 벨트 아래에서 이동하는 경우는 존재하지 않습니다.

 

 3. 벨트의 번호를 1 ~ 2N이 아닌 0 ~ 2 * N - 1이라고 한다면 벨트가 움직이거나 로봇이 움직일 때, 로봇이 있는 벨트의 번호를 %(2*N) 모듈러 연산을 사용해 간단히 알 수 있습니다.

 

코드

#include <bits/stdc++.h>
using namespace std;

struct P {
	int w, in;
};

int n, k, ipt, cnt, len;
deque<int> r; // 로봇이 있는 벨트번호를 담는 덱
deque<P> a; // 벨트의 내구도 w와, 로봇존재여부 in을 담는 덱

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

	cin >> n >> k;
	len = 2 * n;
	for (int i = 0; i < len; i++) {
		cin >> ipt;
		a.push_back({ ipt,0 });
	}
	for (int i = 1;; i++) {
		// #1 벨트의 회전
		a.push_front(a.back()); a.pop_back();

		// 벨트가 회전함에 따라 로봇도 같이 이동
		for (int j = 0; j < r.size(); j++)
			r[j] = (r[j] + 1) % len;

		// 로봇이 n - 1 칸이면 바로 내려줌
		if (!r.empty() && r.front() == n - 1) {
			a[n - 1].in = 0;
			r.pop_front();
		}
		// #2 로봇의 이동
		for (int j = 0; j < r.size(); j++) {
			int next = (r[j] + 1) % len;
			if (!a[next].in && a[next].w >= 1) {
				a[next].in = 1; // 다음칸이 비어있고 내구도가 1이상이면 이동
				a[next].w--; // 내구도 깎아줌
				if (!a[next].w) cnt++;
				a[r[j]].in = 0; // 이동하기 전 칸은 비워줌
				r[j] = next; // 로봇의 위치이동
			}
		}
		// 로봇이 n - 1 칸이면 바로 내려줌
		if (!r.empty() && r.front() == n - 1) {
			a[n - 1].in = 0;
			r.pop_front();
		}
		// 첫번째칸에 로봇이 존재하지않는다면 탑승
		if (!a[0].in && a[0].w >= 1) {
			a[0].in = 1, a[0].w--;
			r.push_back(0);
			if (!a[0].w) cnt++;
		}
		if (cnt >= k) {
			cout << i;
			break;
		}
	}
}