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

문제 링크
https://www.acmicpc.net/problem/16194

최종 코드(정답)

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

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());
       String[] data = br.readLine().split(" ");
       int[] dp = new int[n + 1];

       for (int i = 1; i <= n; i++) {
           dp[i] = Integer.parseInt(data[i - 1]);

           for (int j = 1; j <= i / 2; j++) {
               dp[i] = Math.min(dp[i], dp[j] + dp[i - j]);
           }
       }
        System.out.println(dp[n]);
    }
}

풀이
왜 i-j를 하냐면, i는 전체 카드팩의 수를 나타내고, j는 현재 사려는 카드팩의 개수이기 때문이다.
i-j를 하게 되면, 전체에서 현재 카드팩 수를 뺀 남은 카드팩 수가 나온다.

dp[i-j] => 필요한 카드팩 수가 있는 카드팩의 가격을 얻을 수 있다.

i/2를 하는 이유 : 중복을 제거하려고

예를 들어, i가 4라고 가정해봅시다.
j가 1, 2, 3일 때 i-j는 각각 3, 2, 1입니다. j가 3을 넘어가면 j와 i-j의 값이 단지 바뀌는 것뿐이므로, 이런 중복을 피하기 위해 j <= i / 2로 제한하는 것입니다.

다들 값 초기화를 할 때 dp[i]를 MAX_VALUE로 초기화하라고 한다. (10001이다 여기서는)
근데 사실 없어도 정답이다.