[백준] [c++] 15685번 드래곤 커브

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

15685번: 드래곤 커브

문제 드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다. 시작 점 시작 방향 세대 0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다. 1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 ...

www.acmicpc.net

​

1) 걍 시뮬레이션??? -> 구현실패 & 시간초과

2) 규칙이 있나보다 -> 이틀동안 생각하다가 모르겠어서 구글링

​

(규칙)

이전꺼 역순으로 +1한거 만큼 더 감

​

​

g

0 : 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 4(0) 3 2 3 2 1

​

스택을 사용하여서 나중에 들어온 녀석을 먼저 꺼내서 +1 해서 다음 세대에 넣어주었다

규칙발견하면 순식간에 푸는 문제

 

#include <iostream>
#include <stack>
using namespace std;

int arr[101][101];

int main() {
	int n;
	int x, y, d, g;
	cin >> n;
	while (n--) {
		cin >> x >> y >> d >> g; //x,y 시작점 d 방향 g 세대
		stack<int>dir;
		stack<int>temp;
		dir.push(d);
		temp.push(dir.top());
		arr[x][y] = 1;
		for (int i = 1; i <= g; i++) {
			while (!temp.empty()) {
				dir.push((temp.top() + 1)%4);
				temp.pop();
			}
			temp = dir;
		}
		stack<int> result;
		while (!dir.empty()) {
			result.push(dir.top());
			dir.pop();
		}
		/*while (!result.empty()) {
			cout << result.top() << " ";
			result.pop();
		}
		cout << endl;*/
		while (!result.empty()) {
			int a = result.top();
			result.pop();
			switch (a) {
			case 0:
				x = x + 1;
				arr[x][y] = 1;
				break;
			case 1:
				y = y - 1;
				arr[x][y] = 1;
				break;
			case 2:
				x = x - 1;
				arr[x][y] = 1;
				break;
			case 3:
				y = y + 1;
				arr[x][y] = 1;
				break;
			}
		}

	}
	int  cnt = 0;
	for (int i = 0; i <= 100; i++) {
		for (int j = 0; j <= 100; j++) {
			if (arr[i][j] == 1 && arr[i + 1][j] == 1 && arr[i][j + 1]==1 && arr[i + 1][j + 1] == 1) {
				cnt++;
			}
		}
	}
	cout << cnt;
}