[BOJ] 백준 15918 랭퍼든 수열쟁이야!!

문제 링크

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

언뜻보면 어려워 보이지만 n의 범위가 작기때문에 백트래킹으로 가능한 자리에 하나하나 다 넣어보면 쉽게 풀린다.

비어있는 i번째 자리에 어떤 수 num을 넣고 싶으면 (i+num+1)번째 자리가 비어있는지 확인하면 된다.

시간복잡도는 대충 O((N-2)!)인데 불가능한 자리가 많으므로 저거보다 훨씬 덜 나온다.

정답 코드

	#include <iostream>
	using namespace std;
	int n, x, y, t;
	int p[25];
	int foo(int num) {
	if (num == t) return foo(num + 1);
	if (num == n + 1) {
	return 1;
	}
	int cnt = 0;
	for (int i = 1; (i + num + 1) < 2 * n + 1; i++) {
	if (p[i] == 0 && p[i + num + 1] == 0) {
	p[i] = p[i + num + 1] = num;
	cnt += foo(num + 1);
	p[i] = p[i + num + 1] = 0;
	}
	}
	return cnt;
	}
	int main() {
	cin >> n >> x >> y;
	t = y - x - 1;
	p[x] = p[y] = t;
	cout << foo(1);
	}

view raw 15918.cpp hosted with ❤ by GitHub

질문, 피드백 환영합니다.