백준 16194 자바 - 카드 구매하기2

문제

---

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

16194번: 카드 구매하기 2

 

 

 

문제해결

---

- 11052 카드 구매하기 문제와 비슷하다

https://broship.tistory.com/220

- 다만 n개의 카드 구매를 위해 최대값을 구하는게 아니라 최소값을 구하면 된다

import java.util.Scanner;

public class B16194 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n+1];
        for (int i = 1; i <= n; i++) {
            //i개가 들은 팩을 살때
            dp[i] = sc.nextInt();
            //반복문을 돌며 모든 dp[i-j] + dp[j] 의 값중 가장 작은 값을 dp에 저장한다
            for (int j = 1; j <= i/2; j++) {
                dp[i] = Math.min(dp[i], dp[i-j] + dp[j]);
            }
        }
        System.out.println(dp[n]);
    }
}