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

안녕하세요. 이번 포스팅에서는 백준 20055 컨베이어 벨트 위의 로봇 문제를 풀어보도록 하겠습니다.

 

해당 문제는

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

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

 

위 링크에서 확인하실 수 있습니다.

 

이 문제는 대표적인 시뮬레이션 문제입니다. 근데 문제에서 말이 좀 헷갈리게 써있어서, 문제를 파악하는데 시간을 충분히 사용하신 후 코딩에 들어가시는 것을 추천드립니다.

 

문제를 자세히 살펴보시면 결국

container가 1~2N 까지 있는데, 이 중 로봇이 움직이는 부분은 1~N입니다. 따라서 배열을 계속 회전해주면서 문제를 해결하시면 됩니다.

 

저는 robot, container라는 두 개의 벡터를 사용했습니다.

 

robot은 해당 칸에 robot이 존재하는지를 파악하기 위해 만들었고, container는 현재 해당 칸에 있는 벨트가 내구도가 몇이 남았는지를 기록하기 위해 선언했습니다.

 

vector로 선언하면, 회전의 경우 다음과 같이 쉽게 해결할 수 있습니다.

void containerRotate() {
	rotate(container.begin(), container.end()-1, container.end());
	rotate(robot.begin(), robot.end()-1, robot.end());
	robot[n-1] = 0;
}

 

로봇이 N번째 칸(인덱스 상 N-1)에 도착하면 바로 내려야 하기 때문에 회전을 마친 후 N-1칸은 0으로 처리해주었습니다.

 

로봇이 움직이는 메서드는 

N-2번째 인덱스부터 0번째 인덱스까지 (먼저 올라온 로봇부터 처리)

현재 칸에 로봇이 있고 & 다음 칸에 로봇이 없고 & 다음 칸의 내구도가 1 이상인 경우 움직여주었습니다.

void moveRobot() {
	for(int i = n-2; i >= 0; i--) {
		int next = i+1;
		if(container[next] > 0 && robot[next]==0 && robot[i]==1) {
			container[next]--;
			robot[next] = 1;
			robot[i] = 0;
		}
	}
	robot[n-1] = 0;
}

이 메서드역시 마지막에는 n-1번째 칸에 있는 로봇은 바로 내려주었습니다.

 

 

나머지 구현은 쉽게 하실 수 있다고 생각합니다. 

 

이 문제의 핵심은

어떻게 회전하는 방법을 구현할 것인가 & 로봇이 n-1번째 인덱스에 도착할 때마다 바로바로 내려주었는가에 있다고 생각합니다.

 

<전체 소스코드>

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

int n, k;
vector<int> container, robot;
void containerRotate() {
	rotate(container.begin(), container.end()-1, container.end());
	rotate(robot.begin(), robot.end()-1, robot.end());
	robot[n-1] = 0;
}

void moveRobot() {
	for(int i = n-2; i >= 0; i--) {
		int next = i+1;
		if(container[next] > 0 && robot[next]==0 && robot[i]==1) {
			container[next]--;
			robot[next] = 1;
			robot[i] = 0;
		}
	}
	robot[n-1] = 0;
}
void loadRobot() {
	if(container[0] == 0 || robot[0]==1) return;
	robot[0] = 1;
	container[0]--;
}
bool check() {
	int ret = 0;
	for(auto a : container) if(a==0) ret++;
	return ret >= k;
}
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> k;
	container = vector<int> (2*n, 0);
	robot = vector<int> (n, 0);
	for(int i = 0; i < 2*n; i++) cin >> container[i];	
	
	
	int level = 1;
	while(1) {
		containerRotate();
		moveRobot();		
		loadRobot();
		if(check()) break;
		level++;
	}
	cout << level;
	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.