[Algorithm][C++] BOJ 14891 톱니바퀴

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

14891번: 톱니바퀴

 

풀이 핵심

1. 회전 방향을 미리 저장 한다. 회전 시킬 기어와 하나 건너 맞물리는 기어는 회전 시킬 기어와 회전 방향이 같고 나머지 두 개의 기어는 방향이 회전 시킬 기어와 반대이다. 나머지 연산 이용

int cw[4];
for (int i = 0; i < 2; i++) {
  cw[(idx + 2 * i) % 4] = d; // idx는 회전 시킬 기어의 index이다.
  cw[(idx + 2 * i + 1) % 4] = (d == 1 ? -1 : 1);
}

 

2. 회전이 가능 여부를 먼저 결정 한다. 회전 시킬 기어의 오른 쪽에 있는 기어들은 6번째 이빨과 왼쪽 기어의 2번째 이빨을 비교하면 되고 회전 시킬 기어의 왼 쪽에 있는 기어들은 2번째 이빨과 오른쪽 기어의 6번째 이빨을 비교하면 된다.

bool flag[4] = { 0, };
flag[idx] = true; // 회전 시킬 기어는 무조건 회전한다.
for (int i = idx + 1; i < 4; i++) { // 회전 시킬 기어의 오른 쪽
	if (gear[i][6] == gear[i - 1][2]) break; // 이빨의 극성이 같으면 그 뒤 기어들도 회전 X
	flag[i] = true;
}
for (int i = idx - 1; i >= 0; i--) { // 회전 시킬 기어의 왼 쪽
	if (gear[i][2] == gear[i + 1][6]) break; // 이빨의 극성이 같으면 그 앞 기어들도 회전 X
	flag[i] = true;
}

 

3. 톱니가 회전(시계/반시계 방향)하는 것을 deque로 구현

...
// 시계 방향 회전
tmp = gear[i].back();
gear[i].pop_back();
gear[i].push_front(tmp);
...
// 반시계 방향 회전
tmp = gear[i].back();
gear[i].pop_back();
gear[i].push_front(tmp);
...

 

4. 회전 여부 확인용 flag 배열과 회전 방향 확인용 cw 배열을 이용해 톱니바퀴들을 k번 회전 시킨 뒤 기어의 맨 첫번째가 S극(1) 이면 기어의 index에 따른 square를 모두 더한다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <deque>
#include <vector>
using namespace std;

deque <int> gear[4];
int k;
struct DIR { int idx, d; };
vector <DIR> dir;

void game(int idx, int d) {
	int cw[4];
	for (int i = 0; i < 2; i++) {
		cw[(idx + 2 * i) % 4] = d;
		cw[(idx + 2 * i + 1) % 4] = (d == 1 ? -1 : 1);
	}
	bool flag[4] = { 0, };
	flag[idx] = true;
	for (int i = idx + 1; i < 4; i++) {
		if (gear[i][6] == gear[i - 1][2]) break;
		flag[i] = true;
	}
	for (int i = idx - 1; i >= 0; i--) {
		if (gear[i][2] == gear[i + 1][6]) break;
		flag[i] = true;
	}
	for (int i = 0; i < 4; i++) {
		if (flag[i]) {
			int tmp;
			if (cw[i] == 1) {
				tmp = gear[i].back();
				gear[i].pop_back();
				gear[i].push_front(tmp);
			}
			else {
				tmp = gear[i].front();
				gear[i].pop_front();
				gear[i].push_back(tmp);
			}
		}
	}
}

int GetSquare(int n) {
	int ret = 1;
	for (int i = 0; i < n; i++) {
		ret *= 2;
	}
	return ret;
}

int main() {
	int ret = 0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 8; j++) {
			int tmp;
			scanf("%1d", &tmp);
			gear[i].push_back(tmp);
		}
	}
	scanf("%d", &k);
	for (int i = 0; i < k; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		dir.push_back({ a - 1, b });
	}
	for (int i = 0; i < k; i++) {
		game(dir[i].idx, dir[i].d);
	}
	for (int i = 0; i < 4; i++) {
		if (gear[i][0]) {
			ret += GetSquare(i);
		}
	}
	printf("%d", ret);
	return 0;
}