[BOJ] 11052. 카드 구매하기

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int arr[] = new int [N+1];
		for(int i = 1; i <= N; i++) {
			arr[i] = sc.nextInt();
		}
		
		int dp[] = new int [N+1];
		// dp[i] : 카드 i개를 가장 비싸게 살 때 가격. 
		dp[0] = 0;		
		for(int i = 1; i <= N; i++) {
			dp[i] = arr[i];
		}
		
		for(int i = 2; i <= N; i++) {
			for(int j = 1; j <= i/2; j++) {
				dp[i] = Math.max(dp[j]+dp[i-j], dp[i]); 
			}
		}		
		System.out.println(dp[N]);
	}
}