[BOJ/C++] 20055 컨베이어 벨트 위의 로봇 (삼성 기출)

문제

https://www.acmicpc.net/problem/20055

풀이

문제가 당최 뭔소린지 모르겠어서 솔루션 찾아봤다.

문제를 이해 못한 이유

나 : start! 컨베이어 벨트 위에 로봇을 올린다고 생각. 그 후에 벨트 회전
문제 : 로봇이 있든 없든 벨트 회전-> 로봇 있는 칸은 전부 로봇 이동-> 로봇 올리기

나 : 1번째 단계가 뭘 의미하는지..?
문제 : 1~4의 과정이 1번째 단계임

컨베이어 벨트가 회전하는 순서를 알고리즘으로 정리하면

1. 벨트 회전

벨트 회전
로봇 위치 정보 담은 배열도 같이 회전

2. 로봇 이동
컨베이어 벨트에 가장 먼저 올라간 로봇부터 이동
=> N 위치에 도달하면 로봇 내리므로 밑으로 안 가고, 로봇이 위쪽에서만 이동
=> 처음 벨트에 올라간 로봇은 결국 N-1 위치에 있게 되고, 들어온 순서대로 N-2, N-3, ⋯, 1까지 (⚠️배열이라 인덱스가 0부터 시작하는 거 고려해서 코드 작성)

컨베이어 벨트에 가장 먼저 올라간 로봇부터 하나씩 이동시켜주기
	현재 위치에 로봇있고 && 다음 칸에 내구도 1 이상 && 다음 칸에 로봇 없으면
    	로봇 이동(다음칸 내구도 감소, 로봇 위치 배열 변경) //⚠️N 위치에 도달해서 로봇이 내리는 경우 고려해서 로봇 위치 배열 변경

3. 로봇 올리기

내구도 1 이상 && 다음 칸에 로봇 없으면
	로봇 올리기(내구도 감소, 로봇 위치 배열 변경)

4. 종료 O? X?

내구도가 0인 칸의 개수 셈

예시)
컨베이터 벨트 내구도 : 1 2 1 2 1 2

ans = 1
1. 벨트 회전 : 2 1 2 1 2 1
2. 로봇 이동 : 현재 로봇 없음
3. 로봇 올리기 : 1 1 2 1 2 1
4. 종료 X

ans = 2
1. 벨트 회전 : 1 1 1 2 1 2
2. 로봇 이동 : 1 1 0 2 1 2
3. 로봇 올리기 : 0 1 0 2 1 2
4. 종료 O

∴ 답 = 2

코드

#include <iostream>
#include <deque>

using namespace std;

int n, k;
deque<int> dq;
deque<bool> check;

int cnt() {
	int num = 0;
	for (int i = 0; i < dq.size(); i++) {
		if (dq[i] == 0)	num++;
	}
	return num;
}

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

	int ans = 0;
	cin >> n >> k;
	for (int i = 0; i < 2 * n; i++) {
		int tmp;
		cin >> tmp;
		dq.push_back(tmp);
		check.push_back(false);
	}

	while (1) {
		ans++;

		//1.벨트 회전
		dq.push_front(dq.back());
		dq.pop_back();
		check.push_front(check.back());
		check.pop_back();

		if (check[n - 1] == true) //N번째 위치면 로봇 땅에서 내림
			check[n - 1] = false;

		//2.로봇 이동
		for (int i = n - 2; i >= 0; i--) {
			if (check[i] == true && dq[i + 1] >= 1 && check[i + 1] == false) {
				dq[i + 1]--;
				check[i] = false;
				if(i != n-2)
					check[i + 1] = true;
			}
		}

		//3.로봇 올리기
		if (dq[0] >= 1 && check[0] == false) {
			check[0] = true;
			dq[0]--;
		}

		//4.종료 O? X?
		if (cnt() >= k)	break;
	}

	cout << ans;

	return 0;
}