알고리즘) 수열 추측하기(트리 DFS 활용)

문제 ✨

 가장 윗 줄에 1부터 N까지의 숫자가 한개씩 적혀 있다. 그리고 둘째 줄부터 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 한다. N과 가장 밑의 숫자가 주어져있을 때, 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러 개 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력해야 한다.

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

풀이 ✨

 규칙을 찾아야 한다. N이 4이고 F는 16인 경우에, 가장 윗 줄의 숫자들(답)이 3 1 2 4 순서로 있다고 생각해보자. 아래와 같은 역방향 삼각형을 이룰 것이다. 이 때 둘째 줄부터 해당 값들이 더해지는 과정을 모두 써보자.

3 1 2 4
 4 3 6
  7 9
  16

• 두 번째 줄 : 3+1, 1+2, 2+4
• 세 번째 줄 : 3+1+1+2, 1+2+2+4
• 네 번째 줄(마지막 줄) : 3+1+1+1+2+2+2+4

 마지막 값을 보면 가장 윗줄의 숫자들이 각 1개, 3개, 3개, 1개임을 알 수 있다. 여기에 규칙이 있다. 이 숫자들(1 3 3 1)은 다음 값들과 같다. \({3}\mathrm{C}{0},{3}\mathrm{C}{1}, {3}\mathrm{C}{2}, {3}\mathrm{C}{3}\)

따라서, 마지막 줄의 숫자를 예측하기 위해서는 아래의 두 수식을 이용할 수 있다.

$$ F = {n-1}\mathrm{C}{0} + ... + {n-1}\mathrm{C}{n-1} $$

$$ {n}\mathrm{C}{r} = {n-1}\mathrm{C}{r-1} + {n-1}\mathrm{C}{r} $$

import java.util.Scanner;

public class Main {
    static int n;
    static int f;
    static int[][] list; // 전체 재귀(n-1C0 ~ n-1Cn-1)
    static int[] list2; // n의 값이 n - 1인 경우의 수
    static int[] result;
    static boolean[] checked;
    static String answer = "";

    int getCombination(int v, int k) {
        if (list[v][k] == 0) {
            if (v == k || k == 0) list[v][k] = 1;
            else {
                list[v][k] = getCombination(v - 1, k - 1) + getCombination(v - 1, k);
            }
        }

        return list[v][k];
    }

    void DFS(int L, int sum) {
        if (L == n) {
            if (sum == f && answer.length() == 0) {
                for (int x : result) answer += x + " ";
            }
            return;
        }
        else {
            for (int i = 1; i <= n; i++) {
                if (!checked[i]) {
                    checked[i] = true;
                    result[L] = i;
                    DFS(L + 1, sum + (result[L] * list2[L]));
                    checked[i] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        f = sc.nextInt();
        list = new int[n][n];
        list = new int[n];
        checked = new boolean[n + 1];
        result = new int[n];
        for (int i = 0; i < n; n++) {
          list2[i] = main.getCombination(n - 1, i);
        }
        main.DFS(0, 0);
        System.out.println(answer);
    }
}