[16194번] 카드 구매하기 2 ( 최솟값 )

✅ 최소값

위에 푼 카드 구매하기에서 한 번 더 생각해여하는 게, 0일 때 최소값은 항상 0 이므로 반복문에서 dp[i] = price[i] 로 먼저 설정해두자!

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

✅ 코드

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

public class Main {
	static int[] price;
	static int[] dp;

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

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

		st = new StringTokenizer(br.readLine());

		for (int i = 1; i <= n; i++) {
			price[i] = Integer.parseInt(st.nextToken());
		}

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

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