[백준] 15918 랭퍼든 수열쟁이야!! (Javascript)

문제

BOJ15918_랭퍼든 수열쟁이야!!

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim();
const [n, x, y] = input.split(' ').map(Number);
const arr = Array(2 * n + 1).fill(0);
let answer = 0;
arr[x] = y - x - 1;
arr[y] = y - x - 1;
combination(1);
console.log(answer);

function combination(num) {
    if (num === y - x - 1) {
        combination(num + 1);
        return;
    }
    if (num > n) {
        answer++;
        return;
    }
    for (let i = 1; i < 2 * n - num; i++) {
        if (arr[i] === 0 && arr[i + num + 1] === 0) {
            arr[i] = num;
            arr[i + num + 1] = num;
            combination(num + 1);
            arr[i] = 0;
            arr[i + num + 1] = 0;
        }
    }
}

시간 복잡도

$O(n!)$

풀이

n,x,y 가 주어졌을 때 길이 2n의 랭퍼드 수열을 몇 개 만들수 있는지를 묻고있고, 추가로 x번째 수와 y번째 수가 같다는 조건이 있다.

x번째 수와 y번째 수가 같다는 조건을 통해 x번째 수와 y번째 수가 무엇인지 알아낼 수 있다.
예를 들어 x=4, y=10이라고 했을 때, 4번째 수와 10번째 수의 사이에는 5개의 수(y-x-1)가 있고, 따라서 x번째 수와 y번째 수는 5임을 알 수 있다.

x번째와 y번째 위치에 5를 할당해준 뒤 백트래킹을 통해 나머지 빈 칸에 들어올 수 있는 조합을 모두 구해주면 된다.

combination() 함수에 인자로 들어가는 num 은 1부터 시작해서 1씩 증가한다. 그러다가 num이 n+1이 되면(num > n) 커지면 길이 2n의 랭퍼드 수열이 구해진 것이므로 카운트를 1 증가시키고 함수를 종료한다.

combination() 함수 안에 있는 반복문에서 i는 1부터 $2n-num-1$ 까지 1씩 증가하고, 현재 인덱스(i)와 현재 인덱스(i)+num+1 칸이 비어있다면(===0) num값을 두 인덱스의 위치에 저장하고 num을 1증가시키며 재귀호출을 한다.

모든 조합을 구하면 프로그램이 종료되고 정답이 출력된다.