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

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

 

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

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

- if(d[x]>0)으로, 메모리제이션을 확인한다. 없으면 시간 초과발생.

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

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

...

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

 

import java.util.Scanner;

public class BOJ11052 {

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

        for(int i=1;i<=n;i++){
            p[i]=sc.nextInt();
        }
        int d[]=new int[n+1];

        System.out.println(operate(n,p,d));
    }
    static int operate(int x, int[] p,int[] d) {
        if (x == 1) {
            d[x]=p[1];
            return p[1];
        }
        if (d[x] > 0) 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];
    }
}