[DP] 11052 카드 구매하기

• 조건
  • 카드를 N개 구매한다.
  • 인덱스의 범위가 입력받은 N을 넘어서는 안된다
  • 카드백에 들어있는 카드가 작은 것부터 산다.
• 구해야 할 것
  • arr에 입력받는다고 하면 arr을 더한 최대값을 구해야 한다.
• dp에 들어갈 값
  • 각각의 최대값을 대입해서 넣어준다.

import java.util.Scanner;

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