[백준 1821] 수들의 합 (Java)

문제 링크: www.acmicpc.net/problem/1821

1821번: 수들의 합

1. 주의할 점

- 파스칼의 삼각형을 통해 공식을 유추할 수 있어야 한다

 

2. 구현

- 수가 N이면, n-1C0부터 n-1Cn-1까지 총 N개의 수가 나온다. 해당 수들이 위에 배치될 숫자가 나타난 횟수다

- 조합 값을 저장해놓기 위해 Factorial[] 배열을 통해 0!~9!사이의 수를 저장한다

- setMul() 함수를 통해 n-1C0~n-1Cn-1값에 해당하는 값을 Mul[] 배열에 할당한다

- DFS() 함수를 통해 1~N까지의 오름차순으로 순열 구하기 + 순열에 해당하는 값*Mul[]값을 Result에 계속 더하면서 DFS를 수행한다

- Result가 Sum보다 값이 커지거나 이미 Sum을 만족하는 순열을 구한 경우 Return을 수행한다

- 순열을 구했다면 Result와 Sum을 비교하고 Sum과 같다면, 순열을 구했다는 의미로 Finish값을 True로 변경하고 해당 순열을 출력한다

 

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
    static int factorial[],mul[],ans[];
    static int N,sum;
    static boolean check[],finish=false;
    
    static void setMul(){
        for(int i=0;i<N;i++)
            mul[i] = factorial[N-1]/(factorial[N-1-i]*factorial[i]);
    }
    
    static void dfs(int idx, int result){
        if(finish || result>sum) return;
        if(idx==N){
            if(sum==result){
                for(int i=0;i<N;i++)
                    System.out.print(ans[i]+" ");
                finish=true;
            }
            return;
        }
        for(int i=1;i<=N;i++){
            if(!check[i]){
                check[i]=true;
                ans[idx]=i;
                dfs(idx+1,result+mul[idx]*i);
                if(finish) break;
                check[i]=false;
            }
        }
    }
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String ss = br.readLine();
	    StringTokenizer st = new StringTokenizer(ss);
	    N = Integer.parseInt(st.nextToken());
	    sum = Integer.parseInt(st.nextToken());
	    //초기화
	    factorial = new int[N];
	    mul = new int[N];
	    check = new boolean[N+1];
	    ans = new int[N];
	    factorial[0]=1;
	    for(int i=1;i<N;i++)
	        factorial[i] = factorial[i-1]*i;

	    setMul();
	    dfs(0,0);
	}
}