BOJ 20055 컨베이어 벨트 위의 로봇

www.acmicpc.net/problem/20055

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

 

삼성에서 출제된 구현 문제인데 티어가 실버 1이다.

처음엔 문제 이해가 안 됐는데 손으로 천천히 풀어써보니 이해가 갔다.

시뮬레이션 문제 특성상 문제에서 주어진 순서대로 차례차례 풀면 된다.

 

1. 벨트가 한 칸 회전한다.
2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
   1. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
3. 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.
4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.

우리가 구현해야 할 부분은 

 

• 벨트가 한 칸 회전하는 파트
• 로봇을 이동시키는 파트
• 로봇을 '올라가는 위치'에 올리는 파트
• 종료 파트

총 4개이다. 문제를 풀어보면서 1번과 3번, 4번은 쉽게 생각이 되지만 2번 파트는 약간 고민을 해봐야 한다.

 

우선 회전 하는 부분은 따로 함수를 작성해줬다.

 

void rotateBelt(vector<belt>& ar, int s, int e, int k) {
	vector<belt> tmp(ar);

	for (int i = e; i >= k; --i) ar[i] = tmp[i - k];
	for (int i = k - 1, j = 0; i >= 0; i--, j++) ar[i] = tmp[e - j];
}

 

배열이 들어오면 s부터 e까지 k번 오른쪽으로 회전하는 함수인데

인자에 0 ~ 2 * N - 1 구간으로 1번 회전시켜주면 된다.

 

이후에 봐야 할 부분은 로봇을 이동시키는 부분이다. 그전에 만약 '내려가는 위치'에 로봇이 존재한다면 로봇을

내려준다.

 

if (ar[n - 1].isRobot) ar[n - 1].isRobot = false;

 

그 다음은 로봇을 옮기는 부분이다. 먼저 들어온 순서대로 로봇을 이동시켜줘야 하는데

무조건 먼저 들어온 순서대로 나가니 선입선출 자료구조인 큐를 사용해서 풀어도 되지만 

for 문을 역순으로 진행해서 풀어줬다.

 

		for (int i = 2 * n - 1; i >= 0; --i) {
			if (ar[i].isRobot) {
				if (!ar[i + 1].isRobot && ar[i + 1].cap > 0) {
					ar[i].isRobot = false;
					ar[i + 1].isRobot = true;
					ar[i + 1].cap--;
					if (ar[i + 1].cap == 0) cnt++;
				}
			}
		}
		if (ar[n - 1].isRobot) ar[n - 1].isRobot = false;

 

뒤에서부터 진행하면서 로봇이 존재한다면 그다음 칸에 로봇이 없고, 내구도가 0 이상이라면 로봇을 옮겨준다.

이후 내구도가 0이 되었는지 확인해주면 나중에 종료 조건을 처리하기 편하다.

마찬가지로 로봇을 옮긴 후 '내려가는 위치'에 로봇이 존재한다면 내려준다.

 

마지막 조건인 '올라가는 위치'에 로봇이 없고, 내구도가 0 이상이라면 로봇을 올려준다.

 

		if (!ar[0].isRobot && ar[0].cap > 0) {
			ar[0].cap--;
			ar[0].isRobot = true;
			if (ar[0].cap == 0) cnt++;
		}

 

이 4개의 과정을 전부 돌면 한 사이클이 되었으니 카운트를 증가시켜준다.

 

전체 소스 코드

 

#include <iostream>
#include <vector>
using namespace std;

struct belt {
	int cap = 0;
	bool isRobot = false;
};
vector<belt> ar;
int n, k, cnt, ans;

void rotateBelt(vector<belt>& ar, int s, int e, int k) {
	vector<belt> tmp(ar);

	for (int i = e; i >= k; --i) ar[i] = tmp[i - k];
	for (int i = k - 1, j = 0; i >= 0; i--, j++) ar[i] = tmp[e - j];
}

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

	cin >> n >> k;
	ar.resize(n * 2);
	for (int i = 0; i < 2 * n; ++i) cin >> ar[i].cap;

	while (cnt < k) {
		ans++;

		rotateBelt(ar, 0, 2 * n - 1, 1); 
		if (ar[n - 1].isRobot) ar[n - 1].isRobot = false;

		for (int i = 2 * n - 1; i >= 0; --i) {
			if (ar[i].isRobot) {
				if (!ar[i + 1].isRobot && ar[i + 1].cap > 0) {
					ar[i].isRobot = false;
					ar[i + 1].isRobot = true;
					ar[i + 1].cap--;
					if (ar[i + 1].cap == 0) cnt++;
				}
			}
		}
		if (ar[n - 1].isRobot) ar[n - 1].isRobot = false;

		if (!ar[0].isRobot && ar[0].cap > 0) {
			ar[0].cap--;
			ar[0].isRobot = true;
			if (ar[0].cap == 0) cnt++;
		}
	}

	cout << ans << endl;

	return 0;
}

 

구현이 중요한 문제는 STL vector에서 pair로 사용하지 말고 구조체로 선언하는 게 보기 편하다.