수열 추측하기

✅ 어떤 수열을 더해서 최종 값이 나왔는지, 그 수열을 추측하세요

• 첫 줄에 n 개의 숫자가 적혀 있다.
• 둘째줄부터 옆에 있는 숫자끼리 더한다.

• 마지막 나온 값을 저장한다.

• 처음에 n 개의 숫자 개수와 최종값이 주어졌을 때,
• 처음에 주어진 숫자를 구하세요.

class Main {

    static int n; //주어진 숫자 개수
    static int finalNum; //최종 합

    static int[] answer; //1~n까지의 값 저장
    static int[] ch; //1~n까지의 값 저장할 때 중복여부 확인

    static int[] combiArr; //그 레벨 수 저장

    boolean flag = false; //값 찾으면 끝내기

    int[][] combiMemo = new int[35][35]; //메모이제이션

    public int combi(int n, int r) { //nCr
        if(combiMemo[n][r] >0) return combiMemo[n][r];
        if(n==r || r==0) return 1;
        else{
            return combiMemo[n][r] = combi(n-1, r-1) + combi(n-1, r);
        }

    }


    public void DFS(int L, int sum) {
        if(flag) return;
        if(L==n){ //complete
            if(sum == finalNum){
                for(int x: answer){
                    System.out.print(x+" ");
                    flag= true;
                }
            }
        }
        else{ //not complete
            for(int i=1; i<=n; i++){
                if(ch[i] ==0 ){
                    ch[i]=1;
                    answer[L] = i;
                    DFS(L+1, sum+ answer[L]*combiArr[L]);
                    ch[i]=0;


                }
            }

        }

        }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        n= sc.nextInt();
        finalNum = sc.nextInt();
        answer= new int[n];
        combiArr= new int[n];
        ch= new int[n+1];

        for(int i=0; i<n; i++){
            combiArr[i]= T.combi(n-1, i);
        }

        T.DFS(0, 0);

        }
}

//⭐️input:
//4, 16
//⭐️output:
//3 1 2 4

🔵 ThingsILearned

✔️ variables

• answer: 주어진 n개의 숫자를 나열한 방법
  • (1,2,3,4) 또는 (3, 1, 2, 4) 등등
• ch: answer배열을 나열할 때 이 숫자 썼는지 안 썼는지 확인하기 위해 필요
• combiArr: 그 레벨의 수열 저장
• combiMemo: 메모이제이션, 수열(nCr) 저장하고 똑같은 계산 두 번 하지 않도록

✔️ PSVM 함수

• 수열 값 계산해서 combiArr에 저장한다.

✔️ combi 함수

• 수열 계산하는 함수

✔️ DFS 함수