BOJ 20055 : 컨베이어 벨트 위의 로봇 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/20055

 

이후 설명 및 입/출력은 링크 참고

 

시뮬레이션 문제이므로 그대로 구현한다.

 

BELT 구조체는 현재 belt의 번호, 로봇이 있는 경우 로봇의 번호, 그리고 내구도 A가 저장된다.

robot의 번호는 벨트가 최대 200개이고 내구도가 1000이므로, 20만개 정도로 메모리를 잡는다.

robot[i] = i번째 로봇이 현재 있는 belt의 번호이다.

#define MAX (100 + 20)

int N, K;

typedef struct st
{
	int number;
	int robotNumber;
	int A;
}BELT;

BELT belt[MAX * 2];

int changeBelt[MAX * 2];
int robot[200000 + 5000];
int rcnt;

 

벨트의 최초 번호를 그대로 저장하고, 내구도를 저장한다.

그리고 벨트를 이동시키기 위해 changeBelt에 다음 Belt 번호를 저장한다. 

changeBelt[N] = N + 1이 되고 change[2 * N] = 1이 된다.

void input()
{
	scanf("%d %d", &N, &K);

	for (int i = 1; i <= 2 * N; i++)
	{
		scanf("%d", &belt[i].A);
		belt[i].number = i;
	}

	for (int i = 1; i <= 2 * N - 1; i++) changeBelt[i] = i + 1;
	changeBelt[2 * N] = 1;
}

---

rotateBelt는 벨트를 회전한다.

belt 배열은 한 칸씩 밀어내고, robot은 changeBelt 배열을 이용해 같이 한 칸씩 움직인다.

N과 내구도 A가 크면 robot 전체를 움직이는 것은 시간 초과를 내므로,

simulate 함수에서 벨트 위에 있는 robot의 배열인 liveRobot에 대해서만 로봇을 움직인다.

void rotateBelt(int liveRobot[], int liveCount)
{
	BELT tmp = belt[2 * N];
	for (int i = 2 * N - 1; i >= 1; i--) belt[i + 1] = belt[i];
	belt[1] = tmp;

	for (int i = 0; i < liveCount; i++)
	{
		int robotNumber = liveRobot[i];
		robot[robotNumber] = changeBelt[robot[robotNumber]];
	}
}

---

simulate 함수는 아래 조건대로 구현한다.

 

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

하지만 문제는 로봇이 내리는 경우이다.

컨베이어 벨트가 이동한 후, N에 있는 로봇이 내리고, 로봇이 이동한 후, N에 있는 로봇도 내린다.

따라서, 그림의 N + 1 ~ 2 * N 위치에는 로봇이 존재할 수 없다.

 

1은 rotateBelt를 실행하면 된다.

2의 경우는 while문에 아래와 같이 구현한다.

 

먼저, 현재 벨트에 존재하는 로봇의 집합인 liveRobot의 robotNumber만 작업한다.

벨트가 움직여서 robot이 current에 있게 된 경우, robot에 -1 및 belt에 robotNumber를 지운다.

그렇지 않은 경우 changeBelt 배열을 이용해 다음 칸 next을 구한다.

 

next에 robot이 있거나 내구도 A가 0이면 liveRobot에 해당 robotNumber를 저장하고 continue한다.

(로봇이 벨트에서 내려간 것이 아니므로, 다음에도 유효한 robot이다.)

 

로봇이 움직일 수 있다면, belt와 robot 정보를 갱신한다.

이 때, next가 N인 경우에도 마찬가지로 robot을 지우는 작업을 한다.

N이 아닌 경우만 liveRobot 배열에 저장한다.

/* 1. 벨트가 한 칸 회전한다. */
rotateBelt(liveRobot, liveCount);

/* 2. 가장 먼저 벨트에 올라간 로봇부터,
벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다.
만약 이동할 수 없다면 가만히 있는다.*/

int nextLiveCount = 0;

for (int i = 0; i < liveCount; i++)
{
	int robotNumber = liveRobot[i];
	int current = robot[robotNumber];

	if (current == N)
	{
		robot[robotNumber] = -1;
		belt[current].robotNumber = 0;
		continue;
	}

	int next = changeBelt[current];

	/* 2-1) 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며,
	그 칸의 내구도가 1 이상 남아 있어야 한다.*/
	if (belt[next].robotNumber || belt[next].A == 0)
	{
		liveRobot[nextLiveCount++] = robotNumber;
		continue;
	}

	belt[current].robotNumber = 0;
	belt[next].robotNumber = robotNumber;

	belt[next].A--;
	if (belt[next].A == 0) crush++;

	robot[robotNumber] = next;

	if (next == N)
	{
		robot[robotNumber] = -1;
		belt[next].robotNumber = 0;
	}
	else
	{
		liveRobot[nextLiveCount++] = robotNumber;
	}
}

 

3의 경우는 belt[1]에 로봇이 없고, 내구도 A가 0이 아니면 새 로봇을 올리면 된다.

로봇 번호는 rcnt = 1부터 시작해야 belt에 로봇이 있는지 확인이 가능하다.

벨트에 올라간 로봇도 유효한 로봇이므로 liveRobot에 저장한다.

 

4의 경우는 2, 3에서 내구도 감소할 때마다 0이 되는 내구도의 벨트를 crush 변수에 counting한다.

이 때, 벨트의 내구도가 연속해서 0이 될 수 있으므로 crush == K가 아니라 crush >= K로 해야 정상 종료된다.

/* 3. 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다. */
if (belt[1].robotNumber == 0 && belt[1].A != 0)
{
	robot[rcnt] = 1;
	liveRobot[nextLiveCount++] = rcnt;
	belt[1].robotNumber = rcnt++;
	belt[1].A--;
	if (belt[1].A == 0) crush++;
}

/* 4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다. */
liveCount = nextLiveCount;
if (crush >= K) return step;
step++;

 

최종 코드는 아래를 참고하자.

#include <stdio.h>

#define MAX (100 + 20)

int N, K;

typedef struct st
{
	int number;
	int robotNumber;
	int A;
}BELT;

BELT belt[MAX * 2];

int changeBelt[MAX * 2];
int robot[200000 + 5000];
int rcnt;

void input()
{
	scanf("%d %d", &N, &K);

	for (int i = 1; i <= 2 * N; i++)
	{
		scanf("%d", &belt[i].A);
		belt[i].number = i;
	}

	for (int i = 1; i <= 2 * N - 1; i++) changeBelt[i] = i + 1;
	changeBelt[2 * N] = 1;
}

void output()
{
	for (int i = 1; i <= N; i++) printf("(%d, %d, %d)", belt[i].number, belt[i].A, belt[i].robotNumber);
	putchar('\n');
	for (int i = 2 * N; i > N; i--) printf("(%d, %d, %d)", belt[i].number, belt[i].A, belt[i].robotNumber);
	putchar('\n');putchar('\n');
}

void rotateBelt(int liveRobot[], int liveCount)
{
	BELT tmp = belt[2 * N];
	for (int i = 2 * N - 1; i >= 1; i--) belt[i + 1] = belt[i];
	belt[1] = tmp;

	for (int i = 0; i < liveCount; i++)
	{
		int robotNumber = liveRobot[i];
		robot[robotNumber] = changeBelt[robot[robotNumber]];
	}
}

int simulate()
{
	int step, crush, liveCount;
	int liveRobot[MAX * 2] = { 0 };

	liveCount = crush = 0;
	rcnt = step = 1;
	while (1)
	{
		/* 1. 벨트가 한 칸 회전한다. */
		rotateBelt(liveRobot, liveCount);

		/* 2. 가장 먼저 벨트에 올라간 로봇부터,
		벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다.
		만약 이동할 수 없다면 가만히 있는다.*/

		int nextLiveCount = 0;

		for (int i = 0; i < liveCount; i++)
		{
			int robotNumber = liveRobot[i];
			int current = robot[robotNumber];

			if (current == N)
			{
				robot[robotNumber] = -1;
				belt[current].robotNumber = 0;
				continue;
			}

			int next = changeBelt[current];

			/* 2-1) 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며,
			그 칸의 내구도가 1 이상 남아 있어야 한다.*/
			if (belt[next].robotNumber || belt[next].A == 0)
			{
				liveRobot[nextLiveCount++] = robotNumber;
				continue;
			}

			belt[current].robotNumber = 0;
			belt[next].robotNumber = robotNumber;

			belt[next].A--;
			if (belt[next].A == 0) crush++;

			robot[robotNumber] = next;

			if (next == N)
			{
				robot[robotNumber] = -1;
				belt[next].robotNumber = 0;
			}
			else
			{
				liveRobot[nextLiveCount++] = robotNumber;
			}
		}

		/* 3. 올라가는 위치에 로봇이 없다면 로봇을 하나 올린다. */
		if (belt[1].robotNumber == 0 && belt[1].A != 0)
		{
			robot[rcnt] = 1;
			liveRobot[nextLiveCount++] = rcnt;
			belt[1].robotNumber = rcnt++;
			belt[1].A--;
			if (belt[1].A == 0) crush++;
		}

		/* 4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다. */
		liveCount = nextLiveCount;
		if (crush >= K) return step;
		step++;
	}

	return -1; /* impossible case */
}

int main(void)
{
	input();

	printf("%d\n", simulate());

	return 0;
}

 

실제 A형은 tc가 여러 개이므로, belt 배열과 robot의 index인 rcnt를 초기화하는 코드를 넣어야 한다.