[JAVA] 백준 16194번- 카드 구매하기 2

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

16194번: 카드 구매하기 2

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n+1];
        int[] dp = new int[n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=1; i<=n; i++){
            dp[i] = arr[i]; // 카드 i개를 구하는 비용을 i개 카드팩 값으로 초기화
            for(int j=i; j>=1; j--){
                dp[i] = Math.min(dp[i], dp[i-j]+arr[j]);
            }
        }
        System.out.println(dp[n]);
    }
}

 

 

카드 구매하기 문제와 유사한데 이번엔 최솟값을 구하는 문제다.

dp[0]은 0으로 초기화 되어있기 때문에 그대로 사용하면 최솟값은 0이 되어버린다.

그러므로 dp[i]를 arr[i] 로 초기화해 카드 i개를 구하는 비용을 i개 카드팩 값으로 초기화해준다.