백준 15918번, 랭퍼든 수열쟁이야!! 풀이

문제

백준 15918번

풀이

$ x $와 $ y $ 자리가 주어집니다.

문제에서 같은 수는 수열에서 "2번" 나오고, 같은 수 ($ k $) 사이의 원소 개수가 $ k $가 된다고 하였으니,

$ x $와 $ y $ 자리에 넣을 수는 $ y - x + 1 $로 정해집니다.

 

나머지 수를 채우는 방법은 dfs를 사용하여 $ 2^(12) $만큼 돌면서 조건에 맞게 수열을 채워주면 됩니다.

 

시간 복잡도는 $ O(2^N) $이 됩니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

vi vis, ans;
ll cnt = 0;
int n, x, y;

void dfs() {
	int pos = 0;
	for (int i = 1; i <= 2 * n; i++)
		if (!ans[i]) {
			pos = i;
			break;
		}

	if (!pos) {
		cnt++;
		return;
	}

	for (int k = 1; k <= n; k++) {
		if (!vis[k]) {
			if (pos + k + 1 > 2 * n) break;
			if (ans[pos + k + 1]) continue;

			vis[k] = 1;
			ans[pos] = k;
			ans[pos + k + 1] = k;

			dfs();

			ans[pos] = 0;
			ans[pos + k + 1] = 0;
			vis[k] = 0;
		}
	}
}

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

	cin >> n >> x >> y;
	vis.resize(n + 1);
	ans.resize(n * 2 + 1);

	vis[y - x - 1] = 1;
	ans[x] = y - x - 1;
	ans[y] = y - x - 1;

	dfs();
	cout << cnt;
}