문제 링크: https://www.acmicpc.net/problem/17370

 

수열을 만들어보려고 했는데 도저히 규칙을 못찾아서(OEIS에도 없음) 풀이 검색을 해봤습니다. 검색해보니 그냥 브루트포스였습니다

하긴 2^22이면 대충 400만이니 다 해볼 수 있습니다

 

백트래킹을 하다가 이미 방문한 점이면서 이동 횟수가 n번인 경우만 카운트를 해줍니다.

이때 방문했던 점들을 저장하는 방법은 배열로 해도 되고 map 써도 되는데 좌표가 음수가 될 수 있어서 귀찮으니 그냥 map으로 해줍시다

6방향의 좌표는 정수로 계산해줍시다.

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


map<pair<int, int>, int> visited;
const int dy[] = {2, 1, -1, -2, -1, 1};
const int dx[] = {0, 1, 1, 0, -1, -1};
int cnt;

void backtrack(int y, int x, int dir, int to_move) {
	if (to_move == 0) {
		if (visited.find({ y,x }) != visited.end())
			++cnt;
		return;
	}
	else if (visited.find({ y,x }) != visited.end())
		return;


	visited[{y, x}] = true;

	int dir_right = (dir + 1) % 6;
	int dir_left = (dir + 5) % 6;
	backtrack(y+dy[dir_right], x+dx[dir_right], dir_right, to_move-1);
	backtrack(y+dy[dir_left], x+dx[dir_left], dir_left, to_move-1);

	visited.erase({ y,x });
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	cin >> n;

	visited[{0, 0}] = true;
	backtrack(2, 0, 0, n);
	cout << cnt << '\n';

	return 0;
}
반응형

'Online Judge > 백준' 카테고리의 다른 글

[백준][C++] 1753: 최단경로  (0) 2020.07.20
[백준][C++] 1269: 대칭 차집합  (0) 2020.07.19
[백준][C++] 18917: 수열과 쿼리 38  (0) 2020.07.18
[백준][C++] 1072: 게임  (0) 2020.07.18
[백준][C++] 1051: 숫자 정사각형  (0) 2020.07.17