수열 추측하기

수열 추측하기

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

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

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

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

입력 설명

첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다.
N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.

출력 설명

첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다.
답이 존재하지 않는 경우는 입력으로 주어지지 않는다.

입력

4 16

출력

3 1 2 4

틀린 알고리즘

n = f/2
n을 기준으로 n-1 n+1 이런식으로 뻗어나가는 느낌으로 생각.
이럴 경우에
16 -> 7 9
7 -> 3 4 (방향도 다름)
9 -> ??? 생각한대로라면 4 5 인데 맞지 않음.

모범답안 참고 후 구현 코드

public class 수열추측하기 {
    static int n;
    static int f;
    static int[] b; //combination값 저장하는 배열 예를들어 3c0 3c1 3c2 3c3 값 담는 배열
    static int[] p; //순열 값 예를들어 1 2 3 4
    static int[] check;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        f = in.nextInt();
        b = new int[n];
        p = new int[n];
        check = new int[n+1];

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

        dfs(0,0);
    }

    //순열 구하기
    static boolean flag = false;
    static void dfs(int L,int sum){
        if(flag==true) return;
        if(L == n){
            if(sum==f){
                for(int a: p)
                System.out.print(a+" ");
                flag = true;
            }
        }
        else{
            for(int i=1;i<=n;i++){
                if(check[i]==0){
                    check[i] = 1;
                    p[L] = i;
                    dfs(L+1,sum+(p[L]*b[L]));
                    check[i] = 0;
                }
            }
        }
    }

    //조합 경우의 수
    static int[][] com = new int[35][35];
    static int combi(int n,int r){
        if(com[n][r]>0) return com[n][r];
        if(n==r || r==0) return 1;
        if(n-r==1) return n;
        else return com[n][r] = combi(n-1,r-1) + combi(n-1,r);
    }

}

문제에서 요하는 포인트 2가지
1. 순열 구현
2. 조합 구현

만약 3 1 2 4의 순열이 있을 때
이를 가지고 파스칼 삼각형을 구해보면 이런 식으로 전개됨.

3	1	2	4

   (3+1) (1+2) (2+4)

   (3+1+1+2) (1+2+2+4)

    (3+1+1+2+1+2+2+4)

3 : 1개
1: 3개
2: 3개
4: 1개

개수배열을 b라고 했을 때 1,3,3,1.
각각의 숫자는 3C0 3C1 3C2 3C3의 값들임.

따라서 최종 숫자인 f는 각 숫자와 조합 값을 곱한 값의 총합.