[백준]#1821 수들의 합

문제

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

3 1 2 4
 4 3 6
  7 9
   16

N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러 가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.

입력

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

출력

첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재하지 않는 경우는 입력으로 주어지지 않는다.

예제 입력 1

4 16

예제 출력 1

3 1 2 4

풀이

이 문제는 next permutation 알고리즘을 이용해서 모든 수의 배열을 구한 뒤에 dfs(깊이 우선 탐색) 알고리즘을 이용해서 가장 밑 숫자를 구해서 입력과 비교 후 답을 구할 수 있었다.

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

public class Main {
    static int[] arr;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int F = Integer.parseInt(input[1]);

        arr = new int[N];
        for(int i=1; i<=N; i++)
            arr[i-1] = i;

        if(F==sol(arr)) {
            for(int i=0; i<arr.length; i++) {
                System.out.print(arr[i]+" ");
            }
            return ;
        }

        while(next_permutation()) {
            if(F==sol(arr)) {     //마지막 수가 일치하는 경우 수 배열 출력
                for(int i=0; i<arr.length; i++) {
                    System.out.print(arr[i]+" ");
                }
                return ;
            }
        }
    }

    public static int sol(int[] temp) {
        if(temp.length==2) {        //마지막 수 리턴
            return temp[0]+temp[1];
        }

        if(temp.length==1)  //입력이 1 1 인 경우
            return 1;

        int[] next = new int[temp.length-1];
        int i = 0;
        int j = 1;

        while(j<temp.length) {
            next[i] = temp[i]+temp[j];
            i++;
            j++;
        }

        return sol(next);
    }

    public static boolean next_permutation() {
        int i = arr.length-1;

        while(i>0 && arr[i]<=arr[i-1]) {
            i--;
        }

        if(i<=0) return false;

        int j = arr.length-1;

        while(arr[i-1]>=arr[j])
            j--;

        int temp = arr[j];
        arr[j] = arr[i-1];
        arr[i-1] = temp;

        j = arr.length-1;

        while(i<j) {
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            i++;
            j--;
        }

        return true;
    }
}