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

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

16194번: 카드 구매하기 2

---

1. 풀이

이 문제는 [백준 11052] 카드 구매하기 - 자바와 거의 똑같은 문제이다.

 

이번엔 카드 N개를 구매하는데 최소 비용을 고르는 문제이다.

 

주의할 점은 처음 배열을 선언하면 초기값이 0이므로, 배열의 초기값을 잘 설정해줘야한다.

 

그래서 카드 N개를 구하는 비용을 카드가 N개 들어있는 카드팩으로 초기 설정해주면 쉽게 풀 수 있다.

 

백준님의 경우는 배열의 초깃값을 입력값의 최대 개수와 비용의 입력값 최대값을 곱하여 설정해주었다.

정답은 절대 1000*10000이 넘지 않기 때문에.

또한, 모든 배열을 -1로 설정하여 값을 구했는지 안 구했는지 체크하는 방법을 사용했다.

백준님은 후자의 방법을 더 추천한다.

 

 

---

2. 코드

import java.util.*;


public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] p = new int[1001]; // 카드팩 p[i] : i개 카드가 들어있는 카드팩.
        int[] D = new int[10001]; //
        for(int i = 1; i <= N; i++)
            p[i] = sc.nextInt();

        // 카드 1개부터 N개까지. ( Bottom-Up 방식 )
        for(int i = 1; i <= N; i++){
            D[i] = p[i]; // 최소값 초기화.
            // d[i] = -1;
            for(int j = 1; j <= i; j++){
                D[i] = Math.min(D[i], D[i-j]+p[j]);
                // if (d[i] == -1 || d[i] > d[i-j] + a[j]) {
                //     d[i] = d[i-j] + a[j];
                // }
            }
        }

        System.out.println(D[N]);
        sc.close();
    }
}