문제
카드팩은 1개~N개의 카드가 들어있고 각 팩의 가격이 주어진다. 카드를 정확히 N개 구매할 때 지불할 수 있는 최대 금액을 구한다.
입력
- 첫째 줄: 카드의 수 N (1 ≤ N ≤ 1,000)
- 둘째 줄: 1개~N개짜리 카드팩의 가격 P[1], P[2], ..., P[N]
출력
카드 N개를 구매할 때 최대 금액을 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 1 5 6 7 | 10 |
5 10 9 8 7 6 | 50 |
풀이
dp[n]을 카드를 정확히 n개 구매할 때의 최대 금액으로 정의한다. n개를 구매하는 방법은 i개짜리 카드팩 1개(비용 arr[i])를 사고 나머지 n-i개를 최적으로 구매하는 방식으로 분해된다.
dp배열을 null로 초기화하고 메모이제이션 방식으로recur(N)을 호출한다.recur(n)에서dp[n]이 null이면arr[n]으로 초기값을 설정한다.i를 1부터n-1까지 순회하며recur(n-i) + arr[i]와 비교해 최대값으로 갱신한다.- 계산된
dp[n]을 반환하며 중복 계산을 방지한다.
핵심 아이디어: n개를 구매하는 방법을 n = i + (n-i)로 분해한다. i개짜리 팩을 사고 나머지 n-i개를 재귀적으로 최적화한다. 이를 통해 O(N^2)의 중복 부분 문제를 메모이제이션으로 효율적으로 처리한다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Day95BOJ11052카드구매DP { //
static int N;
static int[] arr;
static Integer[] dp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
arr = new int[N + 1];
dp = new Integer[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i < N + 1; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
System.out.println(recur(N));
br.close();
}
private static int recur(int n) {
if (dp[n] == null) {
dp[n] = arr[n];
for (int i = 1; i < n; i++)
dp[n] = Math.max(dp[n], recur(n - i) + arr[i]);
}
// System.out.println(Arrays.toString(dp));
return dp[n];
}
}
// n = i + (n - i), n개를 구매하는 방법
// 중에 값이 최대일때를 반환한다.
// 예제1 )
// 4
// 1 5 6 7
// dp[4] = dp[4] 또는 dp[3]+arr[1] 또는 dp[2]+arr[2] 또는 dp[1]+arr[3]
// dp[3] = dp[3] 또는 dp[2]+arr[1] 또는 dp[1]+arr[2]
// dp[2] = dp[2] 또는 dp[1]+arr[1]
// dp[1] = dp[1]복잡도
- 시간: O(N^2) — 각 dp[n] 계산 시 n개의 분할 방법 탐색
- 공간: O(N) — dp 배열 및 카드팩 가격 배열