알고리즘 :: 백준 :: 시뮬레이션 :: 15662 :: 톱니바퀴 (2)

문제

문제접근

문제 이해

• 글과 그림이 많은 전형적인 골드급 시뮬레이션 유형 문제입니다.
• 문제 조건을 정리하면 비교적 짧습니다.
  • i번째 톱니바퀴로부터 왼쪽 부분, 오른쪽 부분을 검사.
  • 맞닿은 톱니바퀴가 반대극일 때 반대방향으로 회전. 같다면 무반응.
  • 톱니는 12시 방향부터 표현 → gear[i][8] i번째 톱니바퀴의 톱니는 2차원 배열로 표현 가능
  • 방향 1은 시계방향, -1은 반시계방향
• 가장 까다로운 점은 모든 과정이 동시에 일어난다는 점입니다.
  • PS에서는 동시성을 표현해줄 방법이 없습니다.
  • 따라서, 먼저 검사하는 과정이 필요합니다.
    i번째 톱니바퀴의 왼쪽과 오른쪽을 검사해서 회전이 필요한 톱니바퀴를 검사하는 것입니다.
  • 이 과정은 STL의 lower_bound와 upper_bound를 구하는 과정과 유사합니다.
• 검사를 마쳤다면 해당 톱니바퀴들을 방향을 잘 고려해주면서 회전시킵니다.

코드

배열 방식 (대부분 이렇게 품)

#include <cstdio>

int T, K;
bool gear[1001][8];	// N 0, S 1 

void roll(int num, bool dir) {
	if (dir) {	// clockwise
		bool tmp = gear[num][7];
		for (int i = 7; i > 0; --i)
			gear[num][i] = gear[num][i - 1];
		gear[num][0] = tmp;
	} else {	// counterclockwise
		bool tmp = gear[num][0];
		for (int i = 0; i < 7; ++i)
			gear[num][i] = gear[num][i + 1];
		gear[num][7] = tmp;
	}
}
void solve(int num, bool dir) {
	bool oldDir = dir;
	int left, right;
	for (left = num; left > 1; --left) // left side
		if (gear[left][6] == gear[left - 1][2]) break;
	for (right = num; right < T; ++right) // right side
		if (gear[right][2] == gear[right + 1][6]) break;
	
	roll(num, dir);
	dir = !dir;
	for (int i = num - 1; i >= left; --i) roll(i, dir), dir = !dir;
	dir = !oldDir;
	for (int i = num + 1; i <= right; ++i) roll(i, dir), dir = !dir;
}

int main() {
	int polar = 0, num = 0, dir = 0, ans = 0;
	// Step 1. Input gear information.
	scanf("%d", &T);
	for (int i = 1; i <= T; ++i)
		for (int j = 0; j < 8; ++j)
			scanf("%1d", &polar), gear[i][j] = polar ? true : false;
	// Step 2. Roll gears.
	scanf("%d", &K);
	for (int i = 0; i < K; ++i) {
		scanf("%d %d", &num, &dir);
		solve(num, dir == 1);
	}
	// Step 3. Count and print answer.
	for (int i = 1; i <= T; ++i)
		if (gear[i][0]) ans++;
	printf("%d\n", ans);
}

비트연산 방식

#include <cstdio>
int T, K, gear[1001];

void roll(int num, bool dir) {
	if (dir) {
		bool tmp = gear[num] & 1;
		gear[num] >>= 1;
		if (tmp) gear[num] |= (1 << 7);
	} else {
		bool tmp = gear[num] & (1 << 7);
		gear[num] <<= 1;
		if (tmp) gear[num] |= 1;
	}
}

void solve(int num, bool dir) {
	bool oldDir = dir;
	int left = num, right = num;
	for (; left > 1; --left) {
		bool lhs = gear[left] & (1 << 1);
		bool rhs = gear[left - 1] & (1 << 5);
		if (lhs == rhs) break;
	}
	for (; right < T; ++right) {
		bool lhs = gear[right] & (1 << 5);
		bool rhs = gear[right + 1] & (1 << 1);
		if (lhs == rhs) break;
	}
	roll(num, dir);
	dir = !dir;
	for (int i = num - 1; i >= left; --i) roll(i, dir), dir = !dir;
	dir = !oldDir;
	for (int i = num + 1; i <= right; ++i) roll(i, dir), dir = !dir;
}

int main() {
	int polar = 0, num = 0, dir = 0, ans = 0;
	scanf("%d", &T);
	for (int i = 1; i <= T; ++i) {
		for (int j = 7; j >= 0; --j) {
			scanf("%1d", &polar);
			if (polar) gear[i] |= (1 << j);
		}
	}
	scanf("%d", &K);
	for (int i = 0; i < K; ++i) {
		scanf("%d %d", &num, &dir);
		solve(num, dir == 1);
	}
	for (int i = 1; i <= T; ++i)
		if (gear[i] & (1 << 7)) ans++;
	printf("%d\n", ans);
}

결과