[코드트리] 불안한 무빙워크 (삼성 SW 역량테스트 2020 하반기 오전 1번)

 

SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)

 

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/unstable-moving-walk

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

 

불안한 무빙워크 문제 풀이는 BOJ 20055 : 컨베이어 벨트 위의 로봇과 같다.

#include <stdio.h>

#define MAX (100 + 20)

int T;
int N, K;

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

MOVING moving[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", &moving[i].A);
		moving[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)", moving[i].number, moving[i].A, moving[i].robotNumber);
	putchar('\n');
	for (int i = 2 * N; i > N; i--) printf("(%d, %d, %d)", moving[i].number, moving[i].A, moving[i].robotNumber);
	putchar('\n'); putchar('\n');
}

void rotateBelt(int liveRobot[], int liveCount)
{
	MOVING tmp = moving[2 * N];
	for (int i = 2 * N - 1; i >= 1; i--) moving[i + 1] = moving[i];
	moving[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;
				moving[current].robotNumber = 0;
				continue;
			}

			int next = changeBelt[current];

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

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

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

			robot[robotNumber] = next;

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

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

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

	return -1; /* impossible case */
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

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

	return 0;
}