21.07.12 - [BOJ] 16194. 카드 구매하기 2

[suhyunsim]

문제

• 카드 구매하기 2

핵심 아이디어

• 카드 N개를 구매하는 비용의 최솟값을 구하는 문제

for (int i=1; i<=n; i++) {
    for (int j=1; j<=i; j++) {
        d[i] = min(d[i],d[i-j]+a[j]);
    }
}

• D[0] = 0이기 때문에 min으로 풀 수 없음
• 배열의 초기값을 잘 설정해야 함
  • 1. 카드의 개수 N <= 1000, 카드팩의 가격 <= 10000 : 초기값을 매우 큰 값으로 초기화
  • 2. d[i] = -1로 초기화 -> 아직 정답을 구하지 않았다는 뜻

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q16194;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] d = new int[n + 1];
        int[] p = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            p[i] = sc.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            d[i] = -1;
            for (int j = 1; j <= i; j++) {
                if (d[i] == -1 || d[i] > d[i - j] + p[j]) {
                    d[i] = d[i - j] + p[j];
                }
            }
        }
        System.out.println(d[n]);
    }
}