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

작성일 | In

문제 링크

  • http://icpc.me/15918

문제 출처

  • 제2회 천하제일 코딩대회 C번

사용 알고리즘

  • 백트래킹

시간복잡도

  • O(2n)

풀이

x, y번째 수가 같다는 것은 x, y번째 수가 모두 y-x+1이라는 것을 의미합니다. 그러므로 미리 탐색을 채워주고 시작합시다.

현재 탐색중인 인덱스를 t라고 잡읍시다. 만약 t가 2n이라면 수열을 모두 채운 것이기 때문에 정답을 1 증가시켜줍니다.
만약 t번 인덱스가 아직 채워지지 않았다면, 아직 쓰이지 않은 수 중 삽입 가능한 수 채운 뒤 다음 인덱스부터 재귀적으로 탐색을 합니다.
이미 t번 인덱스가 채워져 있다면 바로 다음 인덱스에서 탐색을 다시 시작하면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

int arr[100];
int chk[100];
int n, x, y;
int cnt;

void f(int t){
	if(t == 2*n){
		cnt++; return;
	}
	if(!arr[t]){
		for(int i=1; i<=n; i++){
			if(chk[i]) continue;
			if(t+i+1<=2*n && !arr[t+i+1]){
				arr[t] = arr[t+i+1] = i;
				chk[i] = 1;
				f(t+1);
				arr[t] = arr[t+i+1] = chk[i] = 0;
			}
		}
	}
  else f(t+1);
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> x >> y;
	arr[x] = arr[y] = y-x-1;
	chk[y-x-1] = 1;
	f(1);
	cout << cnt;
}