[ 백준 ] 15918번 - 랭퍼든 수열쟁이야!! (C++)

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

15918번: 랭퍼든 수열쟁이야!!

 

 

[ 문제풀이 ]

 

1. n, x, y를 입력받고, arr[ x ] = arr [ y ] = y - x - 1로 초기화합니다.

 

2. 백트래킹을 이용하여 수열의 자리를 채우고, 수열이 완성되면 ans++를 해줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
 
using namespace std;
 
int n, x, y;
int arr[25];
int visited[13];
int ans;
 
void dfs(int level)
{
    if (level == 2 * n + 1) {
        ans++;
        return;
    }
    if (arr[level]) dfs(level + 1);
 
    for (int i = 1; i <= n; i++) {
        if (visited[i] == 0 && level + i + 1 <= 2 * n && arr[level] == 0 && arr[level + i + 1] == 0) {
            visited[i] = 1;
            arr[level] = i;
            arr[level + i + 1] = i;
            dfs(level + 1);
            visited[i] = 0;
            arr[level] = 0;
            arr[level + i + 1] = 0;
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> x >> y;
 
    arr[x] = arr[y] = y - x - 1;
    visited[y - x - 1] = 1;
 
    dfs(1);
 
    cout << ans;
}