[백준 15685] 드래곤 커브

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

풀이

1. dx[4]와 dy[4]는 문제에서 주어진대로 선언해야한다.(막 선언하면안됨)

0:오른쪽 1:위 2:왼쪽 3:아래 이므로 , dx[4]={1,0,-1,0}, dy[4]={0,-1,0,1}

2. 규칙을 못찾겠다면 예제1,힌트1을 참고한다.

<규칙>
d =0 시작 기준,

0세대 : 0

1세대 : 0 /1

2세대 : 0 1 /2 1

3세대 : 0 1 2 1 /2 3 2 1

-----------------3세대 까지는 N세대: N-1세대 + N-1세대의 요소의 역순 +1

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

규칙을 못 찾겠거나 3세대까지의 규칙이 4세대이상부터도 똑같이 적용될 걸 의심하는 분들은 예제1과 힌트1을 참고하여 1~3세대규칙을찾고,

4세대부터는 N세대 : N-1세대 + (N-1세대의 요소의 역순 +1) %4 가 됨을 이해한다.

3. 규칙을 찾았다면 직접 그려본다(예제1과 힌트1이있으니 직접 예제1을 그려본다.)

문제에서 사각형의 갯수를 구하라고했는데, 언뜻 보면 뭔소린지 이해가 안 갈 수 있다. 예제1만봐도 사각형이 3개 있으니 3개아닌가?싶을 수 있다.

직접 그려보면 아래 그림처럼 어떤정점에서 칠해진좌표상에서 주어진 순서(0오->1위->2왼->3아래)대로1*1사각형을 그릴 수 있는 정점을 구하는 것임을 알 수 있다.

 

4. 그대로 구현하면된다. 

N-1세대를 이용해서 N세대를 구하고, 그래프상에서 힌트1처럼 입력된 드래곤커브들을 그려서 정점을 체크한다.

좌표가 각각 1세대:2개, 2세대:4개, 3세대: 8개, 4세대 :16개....순으로 이어지므로 아래처럼 작성하면 될 것 같다.

주의 할것은 좌표가 0~100까지이므로 배열선언시 크기를 100*100이아닌 101*101로 선언해야한다.

for (int i = 0; i < g; i++)
		{
			int len = v.size() - 1;
			for (int j = len; j >= 0; j--)
			{
				v.push_back((v[j] + 1) % 4);
			}
		}

코드

#include<iostream>
#include<vector>
using namespace std;
int n, x, y, d, g, ans;
int map[101][101];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,-1,0,1 };
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		vector<int>v;
		cin >> x >> y >> d >> g;
		map[y][x] = 1;
		v.push_back(d);
		for (int i = 0; i < g; i++)
		{
			int len = v.size() - 1;
			for (int j = len; j >= 0; j--)
			{
				v.push_back((v[j] + 1) % 4);
			}
		}
		for (int i = 0; i < v.size(); i++)
		{
			//세대들의 정점을 칠한다.
			y = y + dy[v[i]];
			x = x + dx[v[i]];
			map[y][x] = 1;
		}
	}
	for (int i = 0; i < 100; i++)
	{
		for (int j = 0; j < 100; j++)
		{
			if (map[i][j] && map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1])
				ans++;
		}
	}
	cout << ans << endl;
	
}

결과