[BaekJoon] 백준 11052 카드 구매하기

[BaekJoon] 백준 11052 카드 구매하기

 

문제: https://www.acmicpc.net/problem/11052

 

내코드

 

-DP 문제였다.

주어진 문제에 따르면 점화식은 아래와 같다.

 

카드 N개를 구매할 때 최대 비용 = MAX(i=1~N)(카드 i개 들어있는 카드팩 구매하는 비용 + 카드 N-i개 들어있는 카드팩 구매하는 비용)

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] result = new int[N+1];
        int[] prices = new int[N+1];
        for (int i = 1; i <= N; i++) {
            prices[i] = sc.nextInt();
        }
        for (int i=1;i <= N; i++) {
            for (int j=1;j <= i; j++) {
                result[i] = Math.max(prices[j] + result[i-j], result[i]);
            }
        }
        System.out.println(result[N]);
        sc.close();
    }
}