acmicpc14891.md

톱니바퀴

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

개요

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다.

어떤 톱니바퀴를 회전하였을 때 양 옆에 있는 톱니바퀴가 회전할 수도 있고 회전하지 않을 수도 있다. 회전할 조건은 톱니바퀴의 가장 윗톱니를 0번째 톱니라고 하였을 때 회전한 톱니바퀴의 6번째 톱니와 왼쪽의 회전할 톱니바퀴의 2번째 톱니의 극이 다를 경우이다. 또는 회전한 톱니바퀴의 2번째 톱니와 오른쪽의 회전할 톱니바퀴의 6번째 톱니의 극이 다를 경우이다.

S극은 1, N극은 0으로 표현된다. 가장 위에 있는 톱니가 S극 일 때 점수를 얻는데 이를 계산하는 문제.

분석

톱니바퀴하나는 길이 8인 1차원 배열이 된다. 이 중 가장 윗 톱니를 인덱스 0으로 잡는다면 회전은 가장 윗 톱니를 기준으로 이루어질 수 있다. 예를 들어 시계방향 회전(1)은 가장 윗 톱니 인덱스를 7로 바꾸면 되는데 이는 (원래인덱스(0)-(회전방향)(1)+8)%8 로 계산할 수 있다. 가장 윗 톱니 인덱스가 바뀌면 2번째 톱니와 6번째 톱니의 인덱스도 (가장 윗 톱니 인덱스+ 2 또는 6)%8 으로 계산할 수 있다. 이처럼 나머지 연산을 이용하여 회전을 간단하게 할 수 있다. 원형 큐 또한 나머지연산으로 인덱스를 계산한다.

알고리즘

1. 회전할 톱니의 번호와 방향을 입력받는다.
2. 회전할 톱니의 2번째 톱니와 6번째 톱니를 저장한다.
3. 양 옆으로 진행하며 인접한 톱니들과 톱니를 비교한다.
4. 회전을 해야한다면 회전배열(b[4])에 회전한 톱니와 반대 방향(*-1)의 회전방향을 저장한다.
5. 저장된 회전방향만큼 가장 윗 톱니의 인덱스를 이동시킨다.(t[i]-=b[i], t[i]%=8)

소스

#include <stdio.h>

int top[4][8];

int main()
{
	int i, j, k, t[4], b[4], hn, hb, l, r, flagr, flagl;
	for (i = 0; i < 4; i++)
	{	
		t[i] = 0;
		for (j = 0; j < 8; j++)
		{
			scanf("%c", &top[i][j]);
			top[i][j] -= '0';
		}
		scanf("%c", &k);
	}
	scanf("%d", &k);
	for (i = 1; i <= k; i++)
	{
		for (j = 0; j < 4; j++) b[j] = 0;
		scanf("%d%d", &hn, &hb);
		hn -= 1;
		b[hn] = hb;
		flagr = 1;
		flagl = 1;
		for (j = 1; j < 4; j++)
		{
			l = top[hn-j+1][(t[hn-j+1] + 6) % 8];
			r = top[hn+j-1][(t[hn+j-1] + 2) % 8];
			if (hn + j < 4 && flagr==1)
			{
				if (r != top[hn + j][(t[hn + j] + 6)%8]) b[hn + j] = b[hn + j - 1] * -1;
				else flagr = 0;
			}
			if (hn - j >= 0 && flagl==1)
			{
				if (l != top[hn - j][(t[hn - j] + 2) % 8]) b[hn - j] = b[hn - j + 1] * -1;
				else flagl = 0;
			}
		}
		for (j = 0; j < 4; j++) t[j]=(t[j]-b[j]+8)%8;
	}

	printf("%d", 1 * top[0][t[0]] + 2 * top[1][t[1]] + 4 * top[2][t[2]] + 8 * top[3][t[3]]);
}