백준 15685번 _ 드래곤 커브

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

15685번: 드래곤 커브

 

1. 풀이방법

 

 이 문제는 규칙을 찾아야하는 문제다.

 

 방향 0을 기준으로 규칙을 찾아보면

 

 0 세대 : 0

 1 세대 : 0 1

 2 세대 : 0 1 2 1

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

 

 뭔가 규칙이 보이지 않는가?

 세대가 올라갈수록 늘어나는 부분이 이전세대를 뒤집어놓은 값에 +1해준 값이다.

 

 이 규칙만 찾는다면 나머지는 어렵지않다.

 

 내가 푼 순서대로 이야기하자면

 1) 모든 방향에 대하여 10세대까지의 모든 방향데이터값들을 구해놓기

 2) 들어오는 입력에 대해서 map을 그리기

 3) 사각형이 몇개인지 찾기

 

 순으로 코드를 짜면 정답이다. 

 

---

 

2. 코드 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

int map[105][105];
vector<pair<int, int>>dir = { {1, 0}, {0, -1}, {-1, 0 }, {0, +1} };
vector<vector<vector<int>>>curveData;

// 1) 모든 방향에 대하여 10세대까지의 모든 방향데이터값들을 구해놓기
void makeCurveData(int firstDir)
{
	vector<vector<int>> curve;
	vector<int>pushdata = {firstDir};
	stack<int>reversedata;
	curve.push_back(pushdata);
	//세대가 10세대가 될때까지
	for (int i = 1; i <= 10; i++)
	{
		//뒤집어서 +1 %4해서 stack에 넣기
		for (auto& ele : pushdata)
			reversedata.push((ele + 1) % 4);
		
		while (!reversedata.empty())
		{
			pushdata.push_back(reversedata.top());
			reversedata.pop();
		}
		curve.push_back(pushdata);
	}
	curveData.push_back(move(curve));
}

void curveDataInit()
{
	for (int i = 0; i < 4; i++)
		makeCurveData(i);
}

 2) 들어오는 입력에 대해서 map을 그리기
void drawMap(int x, int y, int d, int g)
{
	map[x][y] = 1;
	//데이터를 찾고 그린다
	for (auto& ele : curveData[d][g])
	{
		x += dir[ele].first;
		y += dir[ele].second;
		map[x][y] = 1;
	}
}

bool isRectangle(int x, int y)
{
	if (map[x + 1][y] && map[x + 1][y + 1] && map[x][y + 1])
		return true;
	return false;
}

3) 사각형이 몇개인지 찾기
int countRectangle()
{
	int cnt = 0;
	for (int x = 0; x <= 100; x++)
	{
		for (int y = 0; y <= 100; y++)
		{
			if (map[x][y] == 1)
			{
				//살펴본다
				if (isRectangle(x, y))
					cnt++;
			}
		}
	}
	return cnt;
}

int main()
{
	curveDataInit();

	int n;
	cin >> n;

	int x, y, d, g;
	for (int i = 0; i < n; i++)
	{
		cin >> x >> y >> d >> g;
		drawMap(x, y, d, g);
	}

	//이제 다그렸으면 네모를 센다
	int answer = countRectangle();
	cout << answer;
	return 0;
}

 

---

 

3. 후기

 

 위에서는 규칙만 찾으면 어렵지 않다고 했는데 규칙찾기가 힘들다.

 나같은 경우에도 처음에 좌표값으로 규칙을 찾아보는 짓으로 시간을 많이 날려먹고 결국 인터넷검색으로 힌트를 찾아 풀었다.