[백준저지] 16194번 : 카드 구매하기2

www.acmicpc.net/problem/16194

16194번: 카드 구매하기 2

1. 문제

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값을 구하는 프로그램을 작성하시오.

2. 풀이

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        int[] p = new int[cnt+1];
        int[] d = new int[cnt+1];
        // 금액 세팅
        for (int i = 1; i <= cnt; i++) {
            p[i] = sc.nextInt();
        }
        for (int i = 1; i <= cnt; i++) {
            for (int j = 1; j <= i; j++) {
                int temp = p[j] + d[i-j];
                // 최소값인지 비교
                if (d[i] > 0) {
                    if (temp < d[i]) {
                        d[i] = temp;
                    }
                } else {
                    d[i] = temp;
                }
            }
        }
        System.out.println(d[cnt]);
    }
}

'카드 구매하기'와 동일하나 최소값을 출력하는 문제.

D[i] => 카드 i개를 구매하는 최소 비용

카드 i개를 구매하는 방법은 => 카드 j개가 들어있는 카드팩을 구매하고, 카드 i-j개를 구매

D[i] = min(P[i] + D[i-j]), 1 <= j <= i

위 점화식을 이용해서 해결.