[DFS, 메모이제이션] 수열 추측하기

설명

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

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

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

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

입력

첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다.

N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.

출력

첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다.

답이 존재하지 않는 경우는 입력으로 주어지지 않는다.

예시 입력 1 

4 16

예시 출력 1

3 1 2 4

 

 

내 풀이 - 다른 풀이 참고

 

문제 설명

 

이 문제의 핵심은 "합을 어떻게 구하는가"이다

 

예시의 3 1 2 4라는 순열로 합을 풀어서 구하면

3 + 1+1+1 + 2+2+2 + 4

맨 왼쪽 오른쪽은 한번씩, 중앙 두개는 3개씩 들어가 있다

개수로만 보면 1개 3개 3개 1개이다

 

즉, n이 4이기에 4-1C0, 4-1C1, 4-1C2, 4-1C3 => 즉 n이 3일때 r이 0부터 n까지의 개수와 같다

따라서 각 숫자와 이에 해당하는 이항 계수를 곱한 뒤의 총합이 f이다

 

이 점을 알고 

https://better21.tistory.com/191

[DFS] 순열 구하기 .java

https://better21.tistory.com/192

[메모이제이션] 조합의 경우의 수

이 두 글에 있는 코드를 참고하면 수월하게 풀 수 있었지만 저 계산식을 구하지 못해 결국 다른 풀이를 보고 풀었다

import java.util.Scanner;


public class Main {
    static int[][] dy  =new int[11][11];//n최대 11
    static int n, f;
    static int[] c, arr, visited;// c이항 계수 배열, arr순열을 저장, visited방문 배열
    static boolean find = false;//하나의 값을 찾음


    public static int cdfs(int n, int r) {
        if(dy[n][r] > 0) return dy[n][r];//이미 계산된 값이 있으면 반환 (메모이제이션)
        if(n==r || r == 0) return 1;//nC0 = 1, nCn = 1
        else return dy[n][r] = cdfs(n-1,r-1) + cdfs(n-1,r);

    }
    public static void dfs(int L, int sum) {//모든 순열을 생성하며 합을 계산
        if(find) return;//찾았으면 더 이상 탐색하지 않음
        if(L == n) {//모든 숫자를 다 사용한 경우
            if(sum==f) {
                for(int x : arr) System.out.print(x + " ");
                find = true;
            }

        }else {
            for(int i =1; i <=n; i++) {//순열에 들어갈 숫자
                //아직 방문하지 않은 숫자인 경우
                if(visited[i] == 0) {
                    visited[i] = 1;
                    arr[L] = i;
                    dfs(L+1,sum+(arr[L] * c[L]));
                    visited[i] = 0;//미방문처리
                }

            }
        }

    }
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        f = sc.nextInt();
        arr = new int[n];
        c = new int[n];
        visited = new int[n+1];//인덱스가 값 -> n까지 사용

        for(int i = 0; i < n; i++) {
            c[i] = cdfs(n-1, i);// n-1Ci를 계산하여 c 배열에 저장

        }
        dfs(0,0);


    }

}