문제 : https://www.acmicpc.net/problem/15685

서론

시뮬레이션 문제.

문제 의도는 파악하지 못했으나 일단은 규칙성을 찾아서 해결

아이디어

보통 회전이란 단어가 나오면 규칙성부터 찾아본다. 경험상 규칙을 찾을 수 있는 경우가 많다.

이 문제는 이동방향에 규칙이 있는데, 문제의 그림에서 규칙성을 찾아보기 위해 이동방향을 순서대로 나열한다.

0세대 : 0 ( 0방향으로 한칸 이동 )

1세대 : 0, 1 ( 0방향으로 이동 후 1방향으로 이동 )

2세대 : 0, 1, 2, 1

3세대 : 0, 1, 2, 1, 2, 3, 2, 1

4세대 : 0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 0, 3, 2, 3, 2, 1

이제 규칙성을 찾을 수 있는데,

3세대 0, 1, 2, 1, 2, 3, 2, 1을 절반으로 나눴을때 앞부분 0, 1, 2, 1은 2세대와 같다.

그리고 뒷부분 2, 3, 2, 1을 또 절반으로 나눠서

나눈것의 앞부분 2, 3은 2세대 앞 절반의 0, 1을 각각 +2%4 한것과 같고( (0+2)%4 = 2, (1+2)%4 = 3 )

나눈것의 뒷부분 2, 1은 2세대 뒤 절반의 2, 1과 같다.

이렇게 이전세대로부터 다음세대의 방향을 예측할 수 있고, 이 규칙성은 0->1세대는 해당되지 않는다. 그래서 0->1세대만 예외처리해주는데, 0-> 1세대의 규칙성은

1세대의 앞부분 0은 0세대와 같고 뒷부분 1은 0세대에서 +1 이다.

구현

// c++

#include <vector>
#include <iostream>

int map[101][101];
int dy[4] = { 0, -1, 0, 1 };
int dx[4] = { 1, 0, -1, 0 };

void dragon(int x, int y, int d, int g) {
	std::vector<int>v;
	int cur = 0;

	v.push_back(d);
	while (cur++ < g) {
		if (cur == 1) v.push_back((d + 1) % 4);
		else {
			for (int i = 0, size = v.size(); i < size ; i++) {
				if (i < size / 2) v.push_back((v[i] + 2) % 4);
				else v.push_back(v[i]);
			}
		}
	}

	map[y][x] = 1;
	for (int i = 0, size = v.size(); i < size; i++) {
		y = y + dy[v[i]];
		x = x + dx[v[i]];
		map[y][x] = 1;
	}
}

int main() {
	int n;
	std::cin >> n;
	while (n--) {
		int x, y, d, g;
		std::cin >> x >> y >> d >> g;
		dragon(x, y, d, g);
	}

	int result = 0;
	for (int i = 0; i < 100; i++) {
		for (int j = 0; j < 100; j++) {
			if (map[i][j] == 1 && map[i + 1][j + 1] == 1 && map[i + 1][j] == 1 && map[i][j + 1] == 1) result++;
		}
	}
	std::cout << result;
}