인프런 08_08 수열 추측하기

📖  문제

---

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

 

예시

• N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오.
• 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.
  • 첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다.
  • N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.
  • 첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다.
  • 답이 존재하지 않는 경우는 입력으로 주어지지 않는다.

출력 예시

⚠️  주의사항

---

• 조합과 메모이제이션 사용하기
• 답이 여러가지 나오는 경우 사전순으로 가장 앞에 오는 것을 출력

 

✍️  이해

---

/**
 * 1. 주어진 입력 받기
 * 2. 8_7 이용해서 메모이제이션 저장
 * 3. line = n일 때 저장해둔 배열 출력
 * 4. for 1~N까지 반복
 *  4-1. check[i] == 0 -> 없는 숫자
 *  4-2. 출력 배열 = i
 *  4-3. DFS(line + 1, sum + 출력배열[L] * 메모배열[L]
 *  4-4. check[i] = 0;
 */

 

✏️  풀이

---

import java.util.Scanner;

public class Main {

    static int n, f;
    static int[] b, p, check;
    // b = combination 저장
    // p = 출력을 위한 배열
    boolean flag = false;
    int[][] memo = new int[35][35];

    public int memoization(int n, int r) {
        if (memo[n][r] > 0) {
            return memo[n][r];
        }

        if (n == r || r == 0) return 1;
        else {
            return memo[n][r] = memoization(n - 1, r - 1) + memoization(n - 1, r);
        }
    }

    public void DFS(int L, int sum) {
        if (flag) return;
        if (L == n) {
            if (sum == f) {
                for (int i : p) System.out.print(i + " ");
                flag = true;
            }
        } else {
            for (int i = 1; i <= n; i++) { // i가 index 번호가 아닌 대입될 숫자
                if(check[i] == 0){
                    check[i] = 1;
                    p[L] = i;
                    DFS(L + 1, sum + (p[L] * b[L]));
                    check[i] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        f = sc.nextInt(); // 마지막 숫자

        b = new int[n];
        p = new int[n];
        check = new int[n + 1]; // 숫자의 시작이 1부터 돌기 때문

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

        T.DFS(0, 0);
    }
}

---