수열 추측하기(DFS)

이 문제는 파스칼의 삼각형과 조합을 이용하여, 주어진 N과 마지막 값 F를 기반으로 가장 윗줄에 들어갈 숫자들을 구하는 문제다. 입력으로 주어지는 N과 F는 각각 삼각형의 가장 윗줄에 위치한 숫자의 개수와 마지막 줄에 나오는 값이다.

 

1. 문제 설명

주어진 N개의 숫자를 파스칼의 삼각형처럼 계산하여, 그 밑줄에 있는 숫자가 주어진 F가 되는 가장 윗줄의 숫자들을 구하는 것이 문제다. 만약 답이 여러 가지가 나올 경우, 사전순으로 가장 앞서는 경우를 출력해야 한다.

 

2. 파스칼의 삼각형과 가중치

파스칼의 삼각형은 아래와 같이 계산되며, 각 숫자가 그 아래 숫자에 얼마나 기여하는지를 이항계수로 계산할 수 있다.

예를 들어, n = 4, 그리고 주어진 윗줄이 3 1 2 4라면 다음과 같은 삼각형이 만들어진다.

이 삼각형에서 숫자가 내려갈 때마다 두 개의 숫자를 더해가며 새로운 숫자를 만든다. 최종적으로 16이라는 숫자가 마지막 줄에 위치하게 된다.

 

3. 해결 전략

1. 이항계수 계산: 각 위치에 있는 숫자가 마지막 값에 얼마나 기여하는지를 계산하기 위해 이항계수를 이용한다.

• 예를 들어, n = 4라면, combi(3, 0), combi(3, 1), combi(3, 2), combi(3, 3) 값을 미리 계산해 두어야 한다.
• 이 값들은 1, 3, 3, 1이 된다.

1. DFS(깊이 우선 탐색): 가능한 모든 숫자 조합을 DFS로 탐색하여, 최종 합이 주어진 F와 같아질 때 정답을 출력한다.
2. 사전순 정렬: 작은 숫자부터 탐색을 시작함으로써, 사전순으로 가장 빠른 답을 구할 수 있다.

4. 코드 설명

package com.example.codingtest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
    static int[] b, p, ch;  // b: 이항계수 기반 가중치, p: 숫자 조합 저장, ch: 사용된 숫자 체크
    static int n, f;  // n: 숫자의 개수, f: 마지막 줄 숫자
    static boolean flag = false;  // 답을 찾으면 종료하기 위한 플래그
    static int[][] dy = new int[35][35];  // 메모이제이션을 위한 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);  // N 값 입력
        f = Integer.parseInt(str[1]);  // F 값 입력
        b = new int[n];  // 가중치 배열 초기화
        p = new int[n];  // 조합 저장 배열 초기화
        ch = new int[n + 1];  // 사용된 숫자 체크 배열 초기화
        for (int i = 0; i < n; i++) {
            b[i] = combi(n - 1, i);  // 이항계수 기반 가중치 계산
        }
        DFS(0, 0);  // DFS 탐색 시작
    }

    public static int combi(int n, int r) {
        if (dy[n][r] > 0) return dy[n][r];  // 이미 계산된 값이 있으면 그 값을 반환
        if (n == r || r == 0) return 1;  // nCn 또는 nC0은 1
        else return dy[n][r] = combi(n - 1, r - 1) + combi(n - 1, r);  // 파스칼의 삼각형 성질을 이용한 이항계수 계산
    }

    public static void DFS(int L, int sum) {
        if (flag) return;  // 이미 답을 찾았으면 더 이상 탐색하지 않음
        if (L == n) {  // 숫자를 모두 선택한 상태
            if (sum == f) {  // 최종 합이 F와 일치하면 답을 찾은 것
                for (int x : p) System.out.print(x + " ");  // 정답 출력
                flag = true;  // 탐색 종료
            }
        } else {
            for (int i = 1; i <= n; i++) {
                if (ch[i] == 0) {  // 아직 사용되지 않은 숫자를 선택
                    ch[i] = 1;  // 사용된 상태로 변경
                    p[L] = i;  // 선택된 숫자를 p 배열에 저장
                    DFS(L + 1, sum + (p[L] * b[L]));  // 다음 숫자를 탐색하며 합을 계산
                    ch[i] = 0;  // 백트래킹: 선택된 숫자를 다시 사용하지 않은 상태로 돌림
                }
            }
        }
    }
}

1. 이항계수 계산 단계 (combi 함수)
   ├── n = 4일 때, 파스칼의 삼각형 이항계수를 이용해 가중치를 계산
   ├── b[0] = combi(3, 0) = 1
   ├── b[1] = combi(3, 1) = 3
   ├── b[2] = combi(3, 2) = 3
   └── b[3] = combi(3, 3) = 1
   └── 결과: b[] = [1, 3, 3, 1]

2. DFS 탐색 (숫자 조합 찾기)
   ├── DFS(0, 0) 시작 (L=0, sum=0)
   │   └── for문을 통해 1부터 n까지 숫자 탐색
   │       ├── i=1 선택 → p[0] = 1, sum += 1 * b[0] = 1
   │       │   └── DFS(1, 1) 호출 (L=1, sum=1)
   │       │       ├── i=2 선택 → p[1] = 2, sum += 2 * b[1] = 7
   │       │       │   └── DFS(2, 7) 호출 (L=2, sum=7)
   │       │       │       ├── i=3 선택 → p[2] = 3, sum += 3 * b[2] = 16
   │       │       │       │   └── DFS(3, 16) 호출 (L=3, sum=16)
   │       │       │       │       ├── i=4 선택 → p[3] = 4, sum += 4 * b[3] = 20 (실패)
   │       │       │       │       └── 백트래킹 후 다른 경우 탐색
   │       │       │       ├── i=4 선택 → p[2] = 4, sum += 4 * b[2] = 19 (실패)
   │       └── i=3 선택 → 다음 숫자 탐색으로 진행
       └── ...
       └── i=3 선택 → p[0] = 3, sum += 3 * b[0] = 3
           └── DFS(1, 3) 호출 (L=1, sum=3)
           ├── i=1 선택 → p[1] = 1, sum += 1 * b[1] = 6
           │   └── DFS(2, 6) 호출 (L=2, sum=6)
           │       ├── i=2 선택 → p[2] = 2, sum += 2 * b[2] = 12
           │       │   └── DFS(3, 12) 호출 (L=3, sum=12)
           │       │       ├── i=3 선택 (이미 사용됨, skip)
           │       │       ├── i=4 선택 → p[3] = 4, sum += 4 * b[3] = 16 (성공)
           │       │       └── 성공! sum == f (16 == 16)
           │       │           └── p 배열 출력: 3 1 2 4


3. 정답 출력 (최종 조건 확인)
   ├── sum == f일 때 (sum=16, f=16)
   └── 가중치와 숫자의 곱셈 과정:
       ├── p[0] * b[0] = 3 * 1 = 3
       ├── p[1] * b[1] = 1 * 3 = 3
       ├── p[2] * b[2] = 2 * 3 = 6
       ├── p[3] * b[3] = 4 * 1 = 4
       └── 합계: 3 + 3 + 6 + 4 = 16 (f와 일치)
       └── p 배열에 저장된 숫자들 출력: 3 1 2 4
       └── 탐색 종료 (flag=true)

5. 코드 설명

1. 이항계수 계산 (combi 함수): 파스칼의 삼각형 성질을 이용해 이항계수를 계산한다. 이 값들은 각 위치에서의 가중치로 사용된다.
2. DFS 함수: 모든 숫자 조합을 탐색하며, 그 합이 주어진 F와 일치하는지 확인한다. 만약 일치하면 그때의 조합을 출력하고 탐색을 종료한다.
3. 백트래킹: 숫자를 선택했다가 다시 돌려놓는 방식으로 모든 경우를 탐색할 수 있도록 한다.

6. 실행 과정 예시

입력: 4 16
출력: 3 1 2 4

1. n = 4, f = 16이 입력된다.
2. 이항계수로부터 가중치 배열 b = [1, 3, 3, 1]이 계산된다.
3. DFS를 통해 1~4까지의 숫자 조합을 탐색하며, 마지막 값이 16이 되는 조합을 찾는다.
4. 첫 번째로 찾은 조합은 3 1 2 4로, 이때 삼각형을 완성하면 마지막 값이 16이 된다.

7. 결론

이 코드는 파스칼의 삼각형과 이항계수를 활용하여 가능한 모든 숫자 조합을 탐색하고, 주어진 조건을 만족하는 조합을 찾아 출력하는 문제다. 이 과정에서 효율성을 높이기 위해 메모이제이션을 활용하여 중복 계산을 방지하고, 백트래킹을 통해 모든 경우의 수를 탐색한다.