N개를 사는 경우
처음에 N개가 들어있는 카드팩을 사는 경우와 N-1개를 가장 비싼 값에 사는 경우(dp[N-1])와 1개가 들어있는 카드팩을 사는 경우를 합한 값과(dp[N-1] +1) 비교하여 dp값을 정한다.
이후 마찬가지로 N-2개를 가장 비싼 값에 사는 경우(dp[N-2])와 2개가 들어있는 카드팩을 사는 경우를 합한 것(dp[N-2] + 2)과 dp[N]을 비교하여서 큰 값을 가진 것을 dp[N]값을 정한다.
import java.util.Scanner;
public class ANS11052 {
static int N;
static int[] dp, cost;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
//dp, cost 선언 및 초기화
dp = new int[N+1];
cost = new int[N+1];
for(int i = 1 ; i <= N; i++){
cost[i] = sc.nextInt();
}
dp[0] = 0;
for(int i = 1; i <= N; i++){
for(int j = 1; j <= i; j++){
dp[i] = Math.max(dp[i], dp[i-j] + cost[j]);
}
}
System.out.println(dp[N]);
}
}