[Algorithm] 수열 추측하기(이항계수, DFS, 메모이제이션)

설명

가장 윗줄에 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

 

풀이 과정.

파스칼 삼각형은 이항계수를 사용하여 조합의 수를 구한다.

예를 들어 삼각형 최상단의 정수가 4개 입력될 경우 3C0/3C1/3C2/3C3 4개의 조합이 생기고 각각의 조합의 수를 combiArr배열에 담아둔다.

* 시간복잡도를 줄이기 위해 2차원 배열을 사용하여 메모이제이션 활용했다.

 

그 다음으로 재귀함수로 순열을 구하면서 순열을 구하는 과정속에서 해당 level(여기선 DFS함수의 매개변수 L로 받았다.)을 PerArr배열(순열)과 combiArr배열(조합)의 index로 사용한다.

즉 0 level에서의 배열의 index는 0이고 1 level에서의 배열의 index는 1이다.

 

해당 level에서 순열을 구하는 동시에 기존에 구해놓은 combiArr배열의 같은 index값을 곱하여 sum에 누적시킨 값과 현재 level+1을 다음 호출 할 재귀함수에 매개변수로 넘긴다.

즉 이런식으로 넘기게 된다. DFS(L+1, sum+(PerArr[L]*combiArr[L])); 

L == n 조건이 참(순열이 한개 완성되는)으로 조건안으로 들어가게 되면 누적된 sum값과 f값을 비교한다.
sum == f 조건이 참일 경우(정답을 찾는 경우) 전역변수에 선언된 boolean타입의 flag값을 true로 바꾼다.

이렇게 되면 재귀함수 내부 첫줄에 있는 if (flag == true) return; 조건으로 인하여 그 후로 호출되는 모든 재귀함수는 바로 빠져 나가게 된다.

 

풀이.

class Main{
    static int n; // 가장 윗줄의 숫자의 개수 (1 ~ N)
    static int f; // 파스칼 삼각형의 맨 아래 값
    static int[] combiArr; // 이항계수를 사용한 조합수 저장 배열
    static int[] PerArr; // 순열 저장 배열
    static int[] perCh; // 순열 체크 배열
    static int[][] dy; // 조합수 메모이제이션 2차원 배열
    boolean flag = false; // 재귀함수 중단 용도로 사용할 플래그 값

    // 이항계수를 사용하여 조합수를 구한 후 b배열에 담아 둔다.
    public int combi(int n, int r){
        if(dy[n][r] > 0) {
            return dy[n][r];
        }
        if(n==r || r==0) {
            return dy[n][r] = 1;
        } else {
            return dy[n][r]=combi(n-1, r-1)+combi(n-1, r);
        }
    }
    
    public void DFS(int L, int sum){ // L - level , sum - 누적 값
        if(flag) return;
        if(L==n){
            if(sum==f){
                for(int x : PerArr) System.out.print(x+" ");
                flag=true;
            }
        } else{
            for(int i=1; i<=n; i++){
                if(perCh[i]==0){
                    perCh[i]=1;
                    PerArr[L]=i;
                    DFS(L+1, sum+(PerArr[L]*combiArr[L]));
                    perCh[i]=0;
                }
            }
        }
    }

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

---

정리 :

파스칼 삼각형 나오면 우선 이항계수 생각해서 각각의 조합 구하고 구한 조합들의 조합의 수를 구한다.

그리고 재귀함수로 순열을 구한 후

구해놓은 조합의 수 배열와 각각의 순열배열의 인덱스끼리 매핑하여 곱한 후 그 값을 누적 시킨후 파스칼 삼각형의 맨 하단의 정수값과 비교한다. 단일이 아니기 때문에 처음으로 찾게되면 바로 끝낸다.

글로는 쓰면서도 헷갈린다. 펜으로 직접 그려가면서 하는게 제일 좋은 방법 같다.