boj, 백준) 20055. 컨베이어 벨트 위의 로봇 ( C / C++ )

1. 문제 링크

www.acmicpc.net/problem/20055

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

2. 문제 개요

길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 컨베이어 벨트를 위아래로 감싸며 돌고 있다.

1번 칸이 '올라가는 위치' N번칸이 있는 위치를 '내려가는 위치'라고 하자. 

 

로봇은 '올라가는 위치'에서만 올라가고 '내려가는 위치'에서만 내려간다. 로봇이 올라가는 곳은(놓거나 걸어서) 내구도가 1 감소한다.

 

컨베이어 벨트를 이용해 로봇들을 건너편으로 옮기려고 하는데, 로봇을 옮기는 과정에서는 아래와 같은 일이 순서대로 일어난다.

 

(1) 벨트가 한 칸 회전함.

(2) 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동. 이동할 수 없다면 가만히 있음. ( 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아있어야 한다)

(3) 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.

(4) 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다.

 

몇 번째 단계에서 그만두는지 출력하는 프로그램을 작성하시오.

 

 

3. 문제 힌트

이 프로그램을 작성하는데 필요한 변수나 함수들을 잘 생각해보자.

(1) 로봇이 놓아짐을 나타내는 변수.

(2) 컨베이어 벨트의 내구도를 나타내는 변수.

(3) 벨트가 한 칸 회전하는 함수.

(4) 로봇을 가장 먼저 벨트로 올라간 순서대로 한 칸씩 이동시키는 함수. 

(5) 로봇을 놓는 함수.

(6) 내구도가 0인 칸의 개수를 나타내는 변수 or 함수

 

이 여섯 가지를 잘 구현해보자.

 

4. 문제 풀이

이 문제는 전형적인 '구현'문제로 특별한 알고리즘이 필요 없다. 그냥 문제에서 제시하는 조건들을 잘 구현하면 된다. 여기서 고려해볼 점은 컨베이어 벨트를 한 칸 회전할 때, 배열로 컨베이어 벨트를 나타내게 될 텐데, 이 값들을 모두 한 칸씩 밀어 복사시켜주면 오버헤드가 상당히 클 것 같다.

그래서 '올라가는 위치(놓는 위치)' & '내려가는 위치'를 움직여 상대적으로 이동하는 것처럼 보이게 해주자.

 

올라가는 위치 : 1, 내려가는 위치 : N에서 컨베이어가 한 칸 움직이면,

올라가는 위치는 2N이 되고, 내려가는 위치는 N-1이 된다. 항상 -1이 되므로, 1 -> 2N이 되는 부분을 조건문으로 걸어서 원형이 되는 것처럼 구현해주어야 한다.

 

밑의 코드에서는 로봇이 존재하면 1, 없으면 0으로 나타내었고, 또, 로봇 배열과 같은 크기의 내구도를 나타내는 벡터도 선언하였다.

 

벨트가 한 칸 회전하기 전에 '내려가는 위치'에 로봇이 있다면 로봇을 없애주자(0으로 변경).

그리고 위에서 얘기한 것처럼, 내려가는 올라가는 위치만 변경해줘서 벨트를 움직이고, 로봇을 움직여야 한다.

 

로봇을 움직일 때는 순서가 있는데, 가장 먼저 올라간 순서대로 움직여라고 했다. 로봇은 컨베이어 벨트에서 앞질러 가지 않기 때문에 따로 순서를 매길 필요는 없으며 내려가는 위치로부터 가까운 순으로 먼저 올라온 것이기 때문에, 내려가는 위치에서 올라가는 위치까지 한번 순회해서 로봇을 한 칸씩 움직여주면 된다. 이때 내구도가 0인지 체크할 필요가 있다.

 

이렇게 로봇을 움직이고 나서는 로봇을 올라가는 위치에 놓을 차례다.

내구도가 0 이상이라면 놓고 내구도를 감소시킨다. 이때 내구도를 감소시키기 때문에, 내구도가 0이 된다면 부서진 컨베이어 벨트라고 카운트 하자. 

 

※ 내구도는 시작부터 0이 되지 않고, 한번 0이 되면 다시 올라가는 일이 없기 때문에, 0이 되는 순간 부서짐을 확정할 수 있다. 그래서 변수 1개로 카운트 가능.

 

밑 코드에 주석처럼 한 번 순회해서 카운트하는 방식으로 했다가(처음에 단순하게 생각) 70ms가 나와서 다른 사람들은 30ms대에 해결하는데 어디서 시간을 줄일 수 있을까 생각해보니 이 부분이 있었습니다.

그래도 시간 초과가 날만큼 연산을 많이 하는 것이 아니기 때문에,, 정답을 원하면 그냥 제출하고 공부를 원하면 더 빠르게 구현해보는 것도 좋음.

 

 

5. 코드

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

int n, k;
vector<int> robot, durability;
int input, output, ans;
int breaknum = 0;

/*int cnt_break()
{
	int breaknum = 0;
	for (int i = 1; i <= 2 * n; ++i)
		if (durability[i] <= 0)
			++breaknum;

	return breaknum;
}*/

void move_belt()
{
	if (input == 1)
		input = 2 * n;
	else
		--input;

	if (output == 1)
		output = 2 * n;
	else
		--output;
	return;
}

void move_robot()
{
	int cur = output;

	while (cur != input)
	{
		if (robot[cur] == 1)
		{
			int next = cur + 1;
			if (next == 2 * n + 1)
				next = 1;

			if (durability[next] > 0 && robot[next] == 0)
			{
				robot[cur] = 0;
				robot[next] = 1;
				--durability[next];
				if (durability[next] == 0)
					breaknum++;
			}
		}

		if (cur == 1)
		{
			cur = 2 * n;
		}
		else
			--cur;		
	}
	return;
}
int main()
{
	scanf("%d %d", &n, &k);
	robot.resize(2 * n + 1);
	durability.resize(2 * n + 1);
	
	for (int i = 1; i <= 2 * n; ++i)
		scanf("%d", &durability[i]);
	
	input = 1, output = n;

	//while (cnt_break() < k)
	while(breaknum < k)
	{
		++ans;

		if (robot[output] == 1)
			robot[output] = 0;
		move_belt();

		if (robot[output] == 1)
			robot[output] = 0;
		move_robot();

		if (durability[input] > 0)
		{
			robot[input] = 1;
			--durability[input];
			if (durability[input] == 0)
				breaknum++;
		}
	}
	printf("%d", ans);
	return 0;
}

 

6. 결과