백준 16194번 카드 구매하기2 (JAVA)

https://www.acmicpc.net/problem/16194

16194번: 카드 구매하기 2

 

저는 해당 문제를 DP를 활용하여 문제를 해결하였습니다. 

해당 DP[depth] = 카드를 살 수 있는 수가 depth만큼 남았을때 최소 값을 가지게 하였습니다. 

 

package BOJ.DP;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_16194 {
    private static final int INF = 987_654_321;
    private static int dfs(int depth, int[] input,int[] dp){
        if(depth < 0){
            return INF;
        }
        if(depth == 0){
            return 0;
        }
        if(dp[depth] != 0){
            return dp[depth];
        }
        int result = INF;
        for(int i = depth ; i > 0 ; i--){
            int share = depth / i;
            for(int j = 1; j <= share ; j++){
                result = Math.min(result, dfs(depth - i * j,input,dp) + j * input[i]);
            }
        }
        dp[depth] = result;
        return result;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(st.nextToken());
        int[] input = new int[n+1];
        int[] dp = new int[n+1];
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 1 ; i <= n ; i++){
            input[i] = stoi.apply(st.nextToken());
        }
        System.out.println(dfs(n,input,dp));
    }
}