문제

문제 링크

해설

• 그림이 많고 복잡해보여서 기선제압을 하는 종류의 시뮬레이션 구현 문제입니다.
• 하지만, 당황하지 마시고, 입력받는 n번째 톱니바퀴를 기준으로 왼쪽으로는 어디까지 같이 회전하는지, 오른쪽으로는 어디까지 같이 회전하는지 구하신 뒤, 문제에서 요구하는대로 서로 반대방향으로 회전하면 됩니다.
• 이때, 회전하면서 이동하지 않도록 합시다. 난도 중상 이상의 시뮬레이션(구현) 문제는 거의 모두 동시성 문제를 안고 있습니다.
  • 이 문제도 예외는 아닙니다. n번째 톱니바퀴를 회전한 뒤 왼쪽/오른쪽으로 이동한다고 가정한다면,
  • 이미 n번째 톱니바퀴가 회전돼있기 때문에 왼쪽/오른쪽 톱니바퀴를 회전해야할지 말지 결정하는 것 자체가 오류입니다. n번째 톱니바퀴의 정보가 오염됐기 때문입니다.
  • 그러므로, 매 회전마다 회전결과를 다른 곳에다가 저장하던지 아니면, 위에서 언급했듯 회전할 범위를 미리 구한 뒤 회전을 한 번에 하는 것이 맞습니다.
• 회전은 std::rotate()를 이용하면 아주 편리하게 할 수 있습니다.
• 어차피, 톱니바퀴도 8칸밖에 안 되기 때문에 비트마스킹보다 std::rotate()를 사용하는 게 성능면으로나 정신적으로나 더 낫습니다 (ㅋㅋ)

int left = n;
for (; left >= 1; --left)
	if (gear[left][6] == gear[left - 1][2]) break;

int right = n;
for (; right < T - 1; ++right)
	if (gear[right][2] == gear[right + 1][6]) break;

• 저는 같이 회전할 왼쪽, 오른쪽 범위를 구하는 코드를 위와 같이 짰습니다.
• n번째 톱니바퀴를 시작으로,
  • 6번 인덱스와 왼쪽의 2번 인덱스가 다르면 회전할 수 있고, 같으면 회전할 수 없습니다.
  • 2번 인덱스와 오른쪽의 6번 인덱스가 다르면 회전할 수 있고, 같으면 회전할 수 없습니다.

int cnt = 0;
for (int i = n; i >= left; --i)
	doRotate(i, (cnt++ & 1) ? !dir : dir);
cnt = 1;
for (int i = n + 1; i <= right; ++i)
	doRotate(i, (cnt++ & 1) ? !dir : dir);

• n번째 톱니바퀴는 명령대로 회전하고, 왼쪽/오른쪽 톱니바퀴는 반대방향으로 회전해야합니다.
• cnt라는 변수를 만들어서 홀수인지 짝수인지 여부로 쉽게 toggle 연산을 수행할 수 있습니다.

코드

#include <bits/stdc++.h>
using namespace std;

int T, K;
string gear[1'001];

void doRotate(int i, bool dir) {
	if (dir) rotate(rbegin(gear[i]), rbegin(gear[i]) + 1, rbegin(gear[i]) + 8);
	else rotate(begin(gear[i]), begin(gear[i]) + 1, begin(gear[i]) + 8);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cin >> T;
	for (int i = 0; i < T; ++i) cin >> gear[i];
	
	cin >> K;
	for (int i = 0; i < K; ++i) {
		int n, d;
		cin >> n >> d;	n--;
		bool dir = (d == -1) ? false : true;
		
		int left = n;
		for (; left >= 1; --left)
			if (gear[left][6] == gear[left - 1][2]) break;
		
		int right = n;
		for (; right < T - 1; ++right)
			if (gear[right][2] == gear[right + 1][6]) break;
		
		int cnt = 0;
		for (int i = n; i >= left; --i)
			doRotate(i, (cnt++ & 1) ? !dir : dir);
		cnt = 1;
		for (int i = n + 1; i <= right; ++i)
			doRotate(i, (cnt++ & 1) ? !dir : dir);
	}
	int ans = 0;
	for (int i = 0; i < T; ++i) if (gear[i][0] == '1') ans++;
	cout << ans;
}

소스코드 링크

결과