백준 15918번 랭퍼든 수열쟁이야!! C++

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

 

백트래킹을 이용하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int n, x, y;
vector<bool> visited_Num(13, false);
vector<bool> visited_Progression(25, false);

int cnt = 0;

void BT(int idx) {
	if (idx == 2 * n) {
		cnt++;
		return;
	}
	if (visited_Progression[idx]) {
		BT(idx + 1);
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (visited_Num[i]) continue;
		if (idx + i + 1 > 2 * n) continue;
		if (visited_Progression[idx + i + 1]) continue;
		visited_Num[i] = true;
		visited_Progression[idx] = true;
		visited_Progression[idx + i + 1] = true;
		BT(idx + 1);
		visited_Num[i] = false;
		visited_Progression[idx] = false;
		visited_Progression[idx + i + 1] = false;
	}
}

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

	cin >> n >> x >> y;
	int initNum = y - x - 1;
	visited_Num[initNum] = true;
	visited_Progression[x] = true;
	visited_Progression[y] = true;
	BT(1);
	cout << cnt;
};