[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 16194

N개의 카드를 1~N개짜리 카드팩으로 고를 때 가장 싸게 사는 가격을 찾기

 

- 1~n개의 카드가 들어있는 카드팩의 가격을 p[1]~p[n] 배열에 저장한다.

- 1~n개의 카드를 고를 때 가장 싸게 가격을 d[1]~d[n] 배열에 저장한다.

- 모든 d[ ] 배열에 초기값은 최대가격을 초과한 10,001로 설정한다.

 

- if(d[x] < 10,001)으로, 메모리제이션을 확인한다.

- x개를 고를 때, x-1개를 가장 싸게 사고, 1개짜리 카드팩을 사는 경우,

x-2개를 가장 싸게 사고, 2개짜리 카드팩을 사는 경우,

...

0개를 가장 싸게 사고, x개짜리 카드팩을 사는 경우까지 가격을 반복문으로 비교하며 최저 가격을 d[x]에 저장한다.

 

import java.util.Scanner;

public class BOJ16194 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[] p=new int[10001];
        int d[]=new int[n+1];

        for(int i=1;i<=n;i++){
            p[i]=sc.nextInt();
            d[i]=10001;
        }
        System.out.println(operate(n,p,d));
    }
    static int operate(int x, int[] p,int[] d) {
        if (x == 1) {
            return p[1];
        }
        if (d[x] <10001) return d[x];

        for(int i=1;i<=x;i++){
            int tmp=operate(x-i,p,d)+p[i];
            if(d[x]>tmp){
                d[x]=tmp;
            }
        }
        return d[x];
    }
}