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

문제링크

• 백준 20055

문제설명

• 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다.
• 벨트가 한 칸 회전하면 1번부터 2N-1번까지의 칸은 다음 번호의 칸이 있는 위치로 이동하고, 2N번 칸은 1번 칸의 위치로 이동한다.
• i번 칸의 내구도는 Ai 이다.
• 컨베이어 벨트 위에 로봇을 올린다.
• 1번은 올리는 위치, N번은 내리는 위치로 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다.
• 로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있고, 로봇을 올리는 위치에 올리거나 로봇이 어떤 칸으로 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다.
• 컨베이어 벨트와 로봇의 이동 과정은 다음과 같다.
  1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
  2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
  • 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
    1. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
    2. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
• 종료되었을 때 몇 번째 단계가 진행 중이었는지 구하라. 가장 처음 수행되는 단계는 1단계이다.

문제접근

• 1번부터 4번 과정을 구현하고, 순서대로 진행해야 한다.
• robot 배열은 올라간 로봇 순서대로 담기는 벡터 컨테이너로 로봇이 올라간 컨베이어 벨트 번호를 담는다.
• belt 배열은 컨베이어 벨트의 내구도를 담는다. 1번부터 2N번까지 있다.
• 벨트가 움직일 때 로봇도 함께 움직이고, 로봇이 내리는 위치에 도달한다면 즉시 내려야한다는 점에 유의한다.

구현

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;

int N, K;
int belt[201]; // 내구도
vector<int> robot; // 로봇의 위치 정보

// 벨트가 각 칸위에 있는 로봇과 함께 한 칸 회전
void moveOne() {
	vector<int> nrobot;
	for (int i = 0; i < robot.size(); i++) {
		// 내리는 위치에 도달하면 즉시 내린다.
		if (robot[i] + 1 == N) {
			continue;
		}
		nrobot.push_back(robot[i]+1);
	}
	robot = nrobot;

	int nbelt[201];
	for (int i = 2; i <= 2 * N; i++) {
		nbelt[i] = belt[i - 1];
	}
	nbelt[1] = belt[2 * N];
	memcpy(belt, nbelt, sizeof(nbelt));
}

// 가장 먼저 벨트에 올라간 로봇부터, 벨트 회전 방향으로 한 칸 이동할 수 있으면 이동하고,
// 이동할 수 없다면 가만히 있는다.
void moveRobot() {
	vector<int> nrobot;
	for (int i = 0; i < robot.size(); i++) {
		int nearIdx = robot[i] + 1;
		// 내구도 확인
		if (belt[nearIdx] < 1) continue;

		// 로봇 유무 확인
		bool flag = false;
		for (int j = 0; j < robot.size(); j++) {
			if (i == j) continue;
			if (nearIdx == robot[j]) {
				flag = true;
				break;
			}
		}
		if (flag) continue;

		belt[nearIdx]--;
		// 움직인 칸이 내리는 칸이면 로봇은 내림
		if (nearIdx == N) robot[i] = -1;
		else robot[i] = nearIdx;
	}

	// update
	for (int i = 0; i < robot.size(); i++) {
		if (robot[i] != -1) nrobot.push_back(robot[i]);
	}
	robot = nrobot;
}

void loadRobot() {
	if (belt[1] > 0) {
		robot.push_back(1);
		belt[1]--;
	}
}

bool checkStrength() {
	int cnt = 0;
	for (int i = 1; i <= 2 * N; i++) {
		if (belt[i] == 0) cnt++;
	}
	if (cnt >= K) return false;
	return true;
}

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

	scanf("%d %d", &N, &K);
	for (int i = 1; i <= 2 * N; i++) {
		scanf("%d", &belt[i]);
	}
	int ans = 1;
	while (true) {
		moveOne();
		moveRobot();
		loadRobot();
		if (checkStrength() == false) break;
		ans++;
	}
	cout << ans << "\n";
	return 0;
}