문제 이해

카드를 N개 구매하고 싶은데, 이 때 돈을 가장 많이 지불해서 구매하고 싶다.
이 때, 카드는 N개보다 크거나 작으면 안되며, "정확히 N개" 구매해야 한다.

지불한 금액의 최댓값을 구하는 문제이다.

---

문제 풀이

i개의 카드가 들어있는 카드팩을 생각해보자.
우리는 이 카드팩에 대하여 2가지 선택을 할 수 있다. 사거나, 사지 않거나
하지만 이 카드팩을 사든 안사든 정확히 N개 구매해야 한다는 조건과 금액의 최댓값을 구해야한다는 조건은 변하지 않을 것이다.

DP[i][j]를 정확히 j개의 카드를 살 때의 최대 비용이라고 생각하고, i는 i개의 카드가 포함되어 있는 카드팩 구매를 고려하는 상황이다.
이 때, i개의 카드팩 구매를 고려할 때는 i-1, i-2, ..., 1개의 카드가 포함되어 있는 카드팩에 대한 가격 비교는 종료되었다고 생각하자.

DP[3][4]를 생각해보자.
나는 정확히 4개의 카드를 선택할 때의 상황을 확인하고 싶다.
DP[3]이기 때문에, 나는 3개의 카드가 포함된 카드팩을 사거나 사지 않을 수 있다.
이 때, 4,5,..의 카드가 포함된 카드팩은 절대로 사지 않을 것이고, 1,2개의 카드가 포함된 카드팩은 살 수도, 사지 않을 수도 있다.

먼저, 정답은 DP[N][N] 공간에 저장될 것이다. N개의 카드를 선택하고, N개의 카드가 포함된 카드팩이 카드팩 중 최고 개수의 카드를 가지고 있는 것이기 때문이다.

DP[i][j]를 구하는 방식은 아래와 같다.

1. DP[i-1][j] : i번째 카드를 선택하지 않고 j개의 카드를 만들고 싶다. i번째 카드를 사용하지 않을 것이므로 i-1번째 카드가 최고 카드이므로, DP[i-1][j] 값을 활용한다.

2. DP[i][j-i] + cost[i] : i번째 카드를 사용하고 싶다. 내가 i개의 카드를 선택했다면 이전에는 j-i개의 카드가 존재해야 할 것이다. 따라서, DP[i][j-i]에는 j-i개의 카드를 선택하는 경우의 수 중 최댓값이 저장되어 있을 것이므로, 해당 값과 i 카드팩의 가격을 더한다.

위 방법으로 보아 행렬은 위 ⇒ 아래로 값이 채워져야 할 것이고, 같은 행이라면 왼쪽 ⇒ 오른쪽으로 값이 채워져야 할 것이다.

점화식은 아래와 같을 것이다.

$DP\left[i\right]\left[j\right]\ =\ \max _{ }^{ }\left(DP\left[i-1\right]\left[j\right],\ DP\left[i\right]\left[j-1\right]+\cos t\left[i\right]\right)$

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static int[][] DP;
    // ans[i][j] -> i : i개의 카드팩을 선택할 것인가 아닌가 확인
    //                  (선택할 경우 vs 선택 안 할 경우)
    //           -> j : 개수를 정확히 j만큼 만들 때의 최솟값
	static int[] cost;
	
	static void pre() {
		for(int j =1;j<N+1;j++) {
			DP[1][j] = cost[1] * j;
		}
	}
	
	static void dp() {
		for(int i =2;i<N+1;i++) {
			for(int j = 1;j<N+1;j++) {
				if(j-i<0) {
					DP[i][j] = DP[i-1][j];
					continue;
				}
				
				int tmp = Math.max(DP[i-1][j], DP[i][j-i]+cost[i]);
				
				DP[i][j] = tmp;
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		cost = new int[N+1];
		DP = new int[N+1][N+1];
		
		for(int i =1;i<N+1;i++) cost[i] = sc.nextInt();
		
		pre();
		dp();

		System.out.println(DP[N][N]);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과