백준 16194번 - 카드 구매하기 2 [DP/자바 JAVA]

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

 

백준 16194번

 

---

사고방식 

카드 구매하기 문제와 아주 똑같은 문제이다. 

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

 

 

유일한 차이점은 이전 문제인 11052번은 최댓값 구하기, 이번 문제는 최솟값 구하기 라는 점이다. 

 

따라서 이전 문제와 점화식은 똑같고, 

 

1) Math.max 대신 Math.min 로 바꿔주면 된다. 

 

다만!!! 여기에 추가로 

2) dp[]를 0이 아닌 Integer.MAX_VALUE로 초기화해줘서 Math.min을 이용할 수 있게 해야한다는 점 

 

만 다르다.

 

 

끝! (그치그치 백사장~ 가끔은 쉽게 가자고~) 

 

---

결론 

dp[i] = Math.min(dp[i], dp[i-j], arr[j])

 

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];
        for(int i=1; i<=n; i++){
            arr[i] = sc.nextInt();
        }
        int dp[] = new int [1002];
        for(int i=1; i<=1001; i++){
            dp[i] = Integer.MAX_VALUE;
        }
        
        for(int i=1; i<=n; i++){
            for(int j=1; j<=i; j++){
                dp[i] = Math.min(dp[i], dp[i-j]+arr[j]);
            }
        }
        System.out.println(dp[n]);
    }
}