Baekjoon 1821 수들의 합 6 JAVA

1821번: 수들의 합 6

문제

가장 윗줄에 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개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재하지 않는 경우는 입력으로 주어지지 않는다.

풀이

가장 윗줄에 만들 수 있는 수열의 최대 길이는 10이다.

숫자 10가지로 만들 수 있는 최대 갯수를 10! 으로 3628800개의 값을 가진다.

순열로 조합하기에 충분한 숫자이기에 모든 경우의 수를 만들고, 각 값들을 문제의 조건에 따라 계산함으로 F가 나올때까지 반복한다.

순열을 만들때 1부터 N의 순서대로 하기에 가장 처음에 나오는 값이 사전순으로 가장 앞에 오는 것이다.

코드

import java.util.*;

public class Main {
	static int n,f;
	static boolean done;
	static int [] num;
	static boolean[] chk;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		n=sc.nextInt();
		f=sc.nextInt();
		chk = new boolean[n+1];
		num = new int[n];
		permu(0);
	}

	public static void permu(int depth) {
		if(depth==n){
			if(done=check(num,n))
				for(int i=0;i<n;i++)
				System.out.print(num[i]+" ");
			return;
		}
		for(int i=1;i<=n;i++) {
			if(!chk[i]) {
				num[depth]=i;
				chk[i]=true;
				permu(depth+1);
				if(done)
					return;
				chk[i]=false;
			}			
		}
	}
	
	public static boolean check(int [] num,int len) {
		int [] temp = new int[len];
		for(int i=0;i<len;i++)
			temp[i]=num[i];
		for(int i=len-1;i>=0;i--) {
			for(int j=0;j<i;j++)
				temp[j]=temp[j]+temp[j+1];
		}
		if(temp[0]==f)
			return true;
		return false;
	}
}