순열 추측하기

설명

가장 윗줄에 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

 

 

문제 해결

 

N과 가장 밑에 있는 숫자(Final Number)가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 문제이다.

문제의 규칙을 찾아보면 아래와 같다.

 

 

각 위치에서의 이항 계수를 저장하는 b배열과 현재 순열을 저장하는 p배열이 있다.

• b[i]는 (n-1)Ci 즉, n-1개의 요소에서 i개를 선택하는 조합의 수를 나타내는 것이고,
• p[i]는 순열의 i번째 위치에 오는 숫자를 저장하는 것이다.

이 둘을 곱해 sum에 누적해가며 이 값이 Final Number와 같아지면 끝내면 된다!

 

예시 코드에서 n = 4이고 f = 16이기에 b배열은 [1, 3, 3, 1]로 초기화되는 것이고,

순열 p는 [1, 2, 3, 4]부터 시작해서 가능한 모든 순열을 탐색해간다.

이 둘을 곱한 것은 sum = p[0]*b[0] + p[1]*b[1] + p[2]*b[2] + p[3]*b[3] 이렇게 되는 것이다.

 

 

코드로 살펴보자.

우선 main 함수에서는

n = in.nextInt();
f = in.nextInt();
b = new int[n];
p = new int[n];
ch = new int[n+1]; //체크 배열 (인덱스가 아니라 값 자체를 사용해야하므로 n+1)
for(int i = 0; i < n; i++){
    b[i] = combi(n-1, i);
}
DFS(0,0);

• 각각 n, f와 b배열, p배열, ch(체크배열)을 입력받고, 초기화해준 후
• combi(n-1, i) 함수는 (n-1)Ci를 계산하여 b[i]에 저장해 b배열을 초기화한다.
  • 즉 예시 입력(n = 4) 에서  b배열은 [1, 3, 3, 1]로 초기화되는 것
    • b[0] = combi(3, 0) = 1
    • b[1] = combi(3, 1) = 3
    • b[2] = combi(3, 2) = 3
    • b[3] = combi(3, 3) = 1

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

• 위 코드는 b배열을 초기화할 때 사용할 조합 코드이다.

 

DFS 함수이다.

static void DFS(int L, int sum){
    if(flag) return;
    if(L == n){ // n개 뽑은 순열이 완성
        if(sum == f){ //sum이 찾는 숫자이면
            for(int x : p)
                System.out.print(x+" ");
            flag = true; //출력 후 flag true로 업데이트
        }
    }

• flag가 true인 경우, 이미 목표 순열을 찾았으므로 함수를 종료한다.
• L이 n과 같다면, 모든 자리를 채운 것이므로 현재 sum이 f와 같은지 확인한다.
  • 같다면 순열을 출력하고 flag를 true로 설정한다.

 

else{
    for(int i = 1; i <= n; i++){ // i 자체가 순열을 만드는 숫자 (인덱스 번호x)
        if(ch[i] == 0) { // i 숫자를 사용하지 않았다면
            ch[i] = 1; // 사용 여부 업데이트
            p[L] = i; //i자체가 데이터
            DFS(L+1, sum+(p[L]*b[L])); //(p[L]*b[L]) 값을 더함
            ch[i] = 0;
        }
    }
}

• 만약 같지 않다면, 1부터 n까지의 숫자를 탐색하며
  • i 를 아직 사용하지 않았다면, ch[i] = 1로 설정해 i를 사용 표시로 바꾼 후 p[L] = i로 순열의 L번째 위치에 i를 저장한다.
  • DFS(L + 1, sum + (p[L] * b[L]))를 호출해 다음 레벨로 이동하며, 현재 위치의 값과 이항 계수를 곱한 값을 sum에 누적해간다.
  • 재귀 호출이 끝나면 ch[i] = 0으로 설정하여 사용 여부를 초기화 시킨다

 

최종 코드

 

import java.util.Scanner;

public class P08_순열추측하기 {
    static int[] b, p, ch;
    static int n;
    static int f; //final number
    static boolean flag = false;
    static int[][] dy = new int[35][35];
    static public int combi(int n, int r){
        if(dy[n][r] > 0) return dy[n][r];
        if(n==r || r==0) return 1;
        else return dy[n][r] = combi(n-1, r-1) + combi(n-1, r);
    }

    static void DFS(int L, int sum){
        if(flag) return;
        if(L == n){ // n개 뽑은 순열이 완성
            if(sum == f){ //sum이 찾는 숫자이면
                for(int x : p)
                    System.out.print(x+" ");
                flag = true; //출력 후 flag true로 업데이트
            }
        }
        else{
            for(int i = 1; i <= n; i++){ // i 자체가 순열을 만드는 숫자 (인덱스 번호x)
                if(ch[i] == 0) { // i 숫자를 사용하지 않았다면
                    ch[i] = 1; // 사용 여부 업데이트
                    p[L] = i; //i자체가 데이터
                    DFS(L+1, sum+(p[L]*b[L])); //(p[L]*b[L]) 값을 더함
                    ch[i] = 0;
                }
            }
        }

    }

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

        n = in.nextInt();
        f = in.nextInt();
        b = new int[n];
        p = new int[n];
        ch = new int[n+1]; //체크 배열 (인덱스가 아니라 값 자체를 사용해야하므로 n+1)
        for(int i = 0; i < n; i++){
            b[i] = combi(n-1, i);
        }
        DFS(0,0);
    }
}