[49일차] 백준 2291 Sequence

package com.algo;

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

/**
 * Created by ibyeongmu on 2017. 3. 25..
 */
public class BJ_2291 {

    static int N,M,K,dp[][][],result[];
    static boolean check[][][];

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader( new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        dp = new int[10+1][2020+1][220+1];
        check = new boolean[10+1][2020+1][220+1];
        result = new int [10+1];
//        System.out.println(proc(N,M,K));
        find(N,1,M,K);
        StringBuilder sb = new StringBuilder();
        for(int i =N;i>0;i--){
            sb.append(result[i]).append(" ");
        }
        System.out.println(sb);



    }
    public static int proc(int idx,int n , int sum){
        if(idx==1){
            if(n<=sum) return 1;
            else return 0;
        }
        if(idx==0)return 0;


        if(check[idx][n][sum])return dp[idx][n][sum];


        check[idx][n][sum]= true;


        for(int i = n ;i<=220;i++) {
            if(sum>=i)dp[idx][n][sum] += proc(idx - 1,i,sum-i);
        }
        return  dp[idx][n][sum];
    }
    public static void find(int n,int num,int sum ,int k){
        if(n==1){
            result[n]=sum;
            return;
        }



        int pivot =0;



            pivot = proc(n - 1, num, sum - num);

        if(k<=pivot ){
            result[n]=num;
            find(n-1,num,sum-num,k);
        }else{
            find(n,num+1,sum,k-pivot);
        }

    }

}