수열 추측하기

! 다시 풀어보기

 

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다.

예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.

N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오.

단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

 

예시 입력 

4 16

예시 출력 

3 1 2 4

이항계수, 순열, 조합을 이용해서 푸는 문제

 

숫자 4개로 햇을때 삼각형의 맨 위에서부터

3c0 3c1 3c2 3c3 형태로 이항계수로 이루어진다

구해둔 이항계수를 배열에 저장하고

dfs를 돌면서 순열을 구해서 각 레벨 인덱스에 있는 이항계수와 순열읍 곱해 원하는 값이 나오는 순열을 찾는 문제다

 

import java.util.*;
class Main{
    static int[] b, p, ch;
    static int n, f;
    boolean flag=false;
    int[][] dy=new int[35][35];
    public int combi(int n, int r){
        if(dy[n][r]>0) return dy[n][r];
        if(n==r || r==0) return 1;
        else return dy[n][r]=combi(n-1, r-1)+combi(n-1, r);
    }

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

    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n=kb.nextInt();
        f=kb.nextInt();
        b=new int[n];
        p=new int[n];
        ch=new int[n+1];
        for(int i=0; i<n; i++){
            b[i]=T.combi(n-1, i);
        }
        T.DFS(0, 0);
    }
}