[백준] 카드 구매하기 2 (16194번 JAVA) / 400 - 다이나믹 프로그래밍 1

[백준] 400 - 다이나믹 프로그래밍 1 : 카드 구매하기 2 (16194번 JAVA)

---

[접근 방법]

 

기본적인 풀이방법은 [11052 카드 구매하기]와 동일하다.

* 추가 해야 할 부분은 카드 i 개의 최솟값을 저장하는 배열인 dp에 초기값을 부여해주어야 한다.

그 이유는 초기값을 부여 해주지 않는 경우, Math.min()을 활용한 비교 과정을 통해 모든 값이 0 이 될 것이다.

---

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

public class Main{

    public static int[] dp;
    public static int[] price;
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        // 가격 저장
        price = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++){
            price[i] = Integer.parseInt(st.nextToken());
        }

        // 최솟값 저장 배열(dp) 초기값 선언
        dp[0] = 0;
        for(int i=1; i<=N; i++){
            dp[i] = price[i];
        }
        
        for(int i=1; i<=N; i++){
            for(int j=1; j<=i; j++){
                dp[i] = Math.min(dp[i], dp[i - j] + price[j]);
            }
        }

        bw.write(dp[N] + "\n");

        bw.flush();
        bw.close();
    }
}