[PS] 인프런 강의 - DFS 8. 수열 추측하기

문제

가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.

 

3 1 2 4
 4 3 6
  7 9
  16

 

N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

 

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

 

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

 

▣ 입력예제 1
4 16

 

▣ 출력예제 1
3 1 2 4

풀이

앞서 배운 조합(Combination)의 경우의 수를 이용해서 풀 수 있다.

 

자꾸 빼먹는데... 주의할 점. 답을 찾은 후 스택 프레임이 삭제되고 이전 주소로 돌아갔을 때 재귀 호출을 바로 종료하도록 flag 값을 사용해야 한다.

 

풀이는 이번에도 손필기! 로 대체한다.

 

 

코드

import java.util.Scanner;

public class Main {

    static int[] p, b, ch; //b: combi에서 뽑아낸 것
    static int n, f;
    static int[][] dy; //combi 메모이제이션
    static boolean flag = false; //주의!! 빼먹지 말 것


    public static void DFS(int L, int sum) {
        if(flag) return;
        if(L == n && sum == f) {
            for(int x : p) System.out.print(x + " ");
            flag = true;
        }
        else {
            //숫자 순회 (i 자체가 숫자)
            for(int i=1; i<=n; i++) {
                if(ch[i] == 0) {
                    p[L] = i;

                    ch[i] = 1;
                    DFS(L+1, sum + (p[L] * b[L]));
                    ch[i] = 0;
                }
            }
        }
    }

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

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        n = in.nextInt(); //1~10
        f = in.nextInt(); //~1,000,000

        p = new int[n];
        b = new int[n];
        ch = new int[n+1]; //1~n

        dy = new int[n+1][n+1];


        for(int i=0; i<n; i++) { //조합
            b[i] = combi(n-1, i); //i는 0~n-1 까지 돌지만 c는 1~n
        }

        DFS(0, 0);

    }
}