백준 16194 카드 구매하기 2 java

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

import java.util.Scanner;


public class Main {

public static void main(String[] args)   {
	 Scanner sc = new Scanner(System.in);
     int n = sc.nextInt();

     int[] arr = new int[n + 1];
     int[] dp = new int[n + 1];

     for (int i = 1; i <= n; i++) {
         arr[i] = sc.nextInt();
         dp[i] = Integer.MAX_VALUE;
        System.out.println(d[i]);
     }

     for (int i = 1; i <= n; i++) {
         for (int j = 1; j <= i; j++) {
             d[i] = Math.min(dp[i], dp[i - j] + arr[j]);
         }
     }

     System.out.println(dp[n]);


}
}

접근법 >

이전 카드 구매하기 1 문제와 아주 흡사하다.
다른 점은 최대 지불값이 아닌 최소 지불값을 구하면 되는 것이다.
하지만 식을
dp[i] = Math.min(dp[i], dp[i - j] + arr[j]);
으로 작성하게 된다면
배열 dp 는 초기값이 0 으로 설정되어있기 때문에 최종 출력값 또한 무조건 0 이 출력되는 문제가 생긴다.

그렇다면 배열 dp 의 값들을 아예 처음부터 자료형 int 의 가장 최대 값으로 설정해주면 어떨까?
그렇게 된다면 dp[i]와 dp[i - j] + arr[j] 에서 i의 값이 1씩 증가할 때 마다 dp[i] 의 초기값이 0 이기 때문에 최소값으로 선택되는 것을 방지 할 수 있다.

Integer.MAX_VALUE 는 int 의 최대값을 의미하며
2147483647 이다. 이를 모든 dp 배열에 넣어주면 원하는 값을 구할 수 있다.