취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15918번 문제인 랭퍼든 수열쟁이야!!이다.
문제는 아래 링크를 확인하자.

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

랭퍼드 수열(Langford sequence; Langford paring)이란 1과 N까지의 자연수들을 각각 두번씩 사용하여 각 i의 사이에 있는 다른 자연수의 개수가 i개가 되게끔 일렬로 나열한 수열이다. 이 문제는 두 정해진 위치에 같은 수를 이용한 랭퍼드 수열의 개수를 세는 문제이다.

두 정해진 위치에 들어갈 수 있는 같은 수는 유일하다는 점을 관찰하자. 나머지 부분에 들어갈 수는 완전탐색으로 찾는 것으로 충분히 빠르게 문제를 해결할 수 있다.

랭퍼드 수열에 대한 더 많은 내용은 아래의 링크를 참고하자.

https://en.wikipedia.org/wiki/Langford_pairing

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int ans = 0;
bool visited[13];
int arr[25];

void func(int idx) {
	if (idx > N) {
		ans++;
		return;
	}
	if (visited[idx]) func(idx + 1);
	else {
		int R = 2 * N - idx - 1;
		for (int i = 1; i <= R; i++) {
			int temp = i + idx + 1;
			if (!arr[i] && !arr[temp]) {
				arr[i] = arr[temp] = idx;
				func(idx + 1);
				arr[i] = arr[temp] = 0;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int x, y; cin >> N >> x >> y;
	arr[x] = arr[y] = y - x - 1;
	visited[y - x - 1] = 1;

	func(1);

	cout << ans;
}