[백준] 16194: 카드 구매하기 2 - JAVA

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

 

풀이

카드팩들의 가격이 주어진다. 카드 i개가 포함된 카드팩의 가격은 Pi원이다.

 

dp 배열을 최대값으로 초기화 해주고, 탐색을 진행했다.

dp[0] + card[n]
dp[1] + card[n - 1]
.
.
.
dp[n] + card[0]

 

`dp[n]` 은 위 경우 중 최소가 되는 값이다.

 

 

---

 

메모리: 14528KB
시간: 144ms
언어: Java 11

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i < n + 1; i++) {
            card[i] = Integer.parseInt(st.nextToken());
            dp[i] = Integer.MAX_VALUE;
        }

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

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

}