[Algorithm] BOJ 11052 - 카드 구매하기

05 Oct 2020 in Devlog on Algorithm

BOJ 11052 - 카드 구매하기

import java.util.Scanner;

public class BOJ11052 {

    public static int[] P;
    public static int[] d;

    public static void main(String[] args) {
        BOJ11052 boj11052 = new BOJ11052();

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        P = new int[n];
        d = new int[n+1];
        for( int i=0 ; i<n ; i++ ){
            P[i] = scan.nextInt();
        }

        int result = 0 ;

        result = boj11052.getMaxPrice(n);

        System.out.println(result);


    }

    int getMaxPrice(int n){
        if(n == 0){
            return 0;
        }

        if(d[n] > 0){
            return d[n];
        }

        for( int i = 1 ; i <= n ; i++ ){
            int temp = P[i-1]+getMaxPrice(n-i);
            d[n] = Math.max(temp,d[n]);
        }


        return d[n];
    }

}