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

풀이

• Dynamic Programming
• 가장 큰 비용으로 n개를 구매하는 방법까지 도달하기 전에 n보다 작은 카드들을 가장 큰 비용으로 구매하는 법들을 기억(memomemoization)해놓고,
  이전에 구했던 값들을 이용해 n개를 가장 큰 비용으로 구매하는 법을 구하는 방식으로 접근해야 하는 문제

i개가 담긴 카드팩의 가격을 저장하는 배열 arr[i]
n개의 카드를 구매하기 위해 지불해야하는 최대 금액을 저장하는 배열 dp[n]

dp[1] = arr[1]
dp[2] = Math.max(arr[1] + dp[2-1] , arr[2] + dp[2-2])
dp[3] = Math.max(arr[1] + dp[3-1] , arr[2] + dp[3-2], arr[3] + dp[3-3])

for(int i=1; i<n; i++)
	for(int j=1; j<=i; j++)
    	dp[i] = Math.max(dp[i], arr[j]+dp[i-j]

코드

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 
 * @author juyoung
 * 
 * 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램
 *
 * parameter
 * 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)
 * 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
 * 
 * return
 * 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값
 * 
 * n장을 갖기 위해 지불해야 하는 최대 금액은 n-i장의 카드를 지불해야 하는 최대 금액들을 순서대로 계산하여 저장한 후 저장된 값들을 이용
 * i개가 담긴 카드팩의 가격을 저장하는 배열 arr[i]
   n개의 카드를 구매하기 위해 지불해야하는 최대 금액을 저장하는 배열 dp[n]
 * DP를 풀때 일반항 형태로 정의하는 것이 중요
 케이스 단위로 생각해보자.
 카드 i개를 구매하는 방법은?
 카드 1개가 들어있는 카드팩을 구매하고, 카드 i-1개를 구입한다.
 카드 2개가 들어있는 카드팩을 구매하고, 카드 i-2개를 구입한다.
 카드 3개가 들어있는 카드팩을 구매하고, 카드 i-3개를 구입한다.
 ...
 카드 i개가 들어있는 카드팩을 구매하고, 카드 0개를 구입한다.
 각 경우를 따지면서 max 값 구함
 
 */

public class boj11052 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		
		int[] card_pack = new int[n+1];
		int[] dp = new int[n+1];

		st = new StringTokenizer(br.readLine(), " ");
		for(int i=1; i<=n; i++) {
			card_pack[i] = Integer.parseInt(st.nextToken()); 
		}
		
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=i; j++) {
				dp[i] = Math.max(dp[i], card_pack[j] + dp[i-j]); // j개의 카드가 들어있는 카트팩을 구매할 때의 케이스
			}
		}
		
		System.out.println(dp[n]);

	}

}