랭퍼든 수열쟁이야!! 15918

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

두 숫자사이의 간격이 정해지면 숫자를 구할수 있다는 사실을 생각해내지 못했다
그리고 dfs 로 완전탐색을 많이 해봤지만 아직도 익숙하지 않아서 구조를 바꾸는게 어렵다
그래서 검색을 해보고 풀었다
그래도 혼자 노력으로 풀어보는 과정이 있어서 풀이를 이해할 수 있었다

시간복잡도는
각 단계에서 n개의 선택지가 있고, 총 2n개의 단계가 있습니다. 즉, 각 단계에서 1부터 n까지의 숫자 중 하나를 선택할 수 있고, 이런 선택을 총 2n번 해야 합니다.

따라서, 백트래킹이 모든 가능한 조합을 탐색한다면, 최악의 경우 시간 복잡도는 O(n^(2n))가 됩니다. 이는 각 단계에서의 선택지 수(n)를 단계의 수(2n)만큼 곱한 것입니다.

코드로 확인해보니
12 1 3
입력하였을때
4920990 횟수 출력되었다

import java.io.*;
import java.util.*;

public class Main {
    static int answer = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");

        int n = Integer.parseInt(input[0]);
        int x = Integer.parseInt(input[1]);
        int y = Integer.parseInt(input[2]);

        int len = n*2+1;

        int[] arr = new int[len];
        boolean[] visit = new boolean[n+1];

        arr[x] = arr[y] = y-x-1;//간격이 정해지면 숫자를 알 수 있다. 1과 5이면 간격이3 이므로 3을 넣어주면된다
        visit[y-x-1] = true;

        search(len, 1, arr, visit, x, y, n);

        System.out.println(answer);
    }
    public static void search(int len, int depth, int[] arr, boolean[] visit, int x, int y, int n) {

        if (depth == len) {
            answer++;
            return;
        }

        if (arr[depth] != 0) {
            search(len, depth + 1, arr, visit, x, y, n);
        } else {
            for (int i = 1; i <= n ; i++) {
                if (false == visit[i] && (depth + i + 1) < len && arr[depth + i + 1] == 0) {
                    visit[i] = true;
                    arr[depth] = i;
                    arr[depth + i + 1] = i;
                    search(len, depth + 1, arr, visit, x, y, n);
                    visit[i] = false;
                    arr[depth] = 0;
                    arr[depth + i + 1] = 0;
                }
            }
        }
    }
}