백준 16194 / 카드 구매하기 2

문제

풀이

설명

카드 N개를 구매해야한다.
카드팩은 총 N가지 종류가 존재한다.
i번째 카드팩은 i개의 카드를 담고있고, 가격은 P[i]원 이다.
카드 N개를 구매하는 비용의 최대값을 구하는 문제

D[i] = 카드i개 구매하는 최대 비용
카드 i개를 구매하는 방법은?
카드 1개가 들어있는 카드팩을 구매하고, 카드 i-1개를 구매
• P[1] + D[i-1]
카드 2개가 들어있는 카드팩을 구매하고, 카드 i-2개를 구매
• P[2] + D[i-2]
…
카드 i-1개가 들어있는 카드팩을 구매하고, 카드 1개를 구매
• P[i-1] + D[1]
카드 i개가 들어있는 카드팩을 구매하고, 카드 0개를 구매
• P[i] + D[0]

D[N] = max(D[n-i]+p[i])
1<=i<=N

코드

import java.util.Scanner;

public class Num16194 {

	public static void main(String[] args) {
		
		 Scanner sc = new Scanner(System.in);
		 
	        int n = sc.nextInt();
	        int[] a = new int[n+1];
	        
	        for (int i=1; i<=n; i++) {
	            a[i] = sc.nextInt();
	        }
	        
	        int[] d = new int[n+1];
	        
	        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] + a[j]) {
	                    d[i] = d[i-j] + a[j];
	                }
	            }
	        }
	        
	        System.out.println(d[n]);
	}

}

코드설명

참고 :
출처 : https://www.acmicpc.net/problem/16194