백준 16194 카드 구매하기(Java)

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

16194번: 카드 구매하기 2

---

 

해석 및 팁

 

---

 

이 문제는 다이내믹프로그래밍을 활용하는 문제입니다.  카드 i개를 구매하는 방법은 1개를 구매한 후 i - 1개를 구입하거나 2개를 구입한 후에 i - 2개를 구입하거나.. j개를 구매한후에 i - j개를 구매하면 됩니다. 따라서 점화식은

dp [i] = arr [j] + dp [i - j]입니다. 

 

---

 

Java 코드

 

---

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;
    }
    dp[1] = arr[1];

    for(int i = 2; 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]);
  }
}