구매액이 최댓값이 될 수 있는 경우는 총 3가지입니다. 예를 들면 카드 10개를 구매하고자 할 때 구매액이 될 수 있는 케이스는 다음과 같습니다.
1. 10장 짜리 카드팩 1개 구매하기 2. i개 짜리 카드팩과 10 - i개 짜리 카드팩을 구매하기 (총 10번이지만 같은 방식이므로 1개 경우로 칩니다) 3. 10이 i로 나누어 떨어지는 경우 i개 짜리 카드팩을 10을 i로 나눈 몫의 수만큼 구매하기 (수에 따라 횟수가 다르지만 같은 방식이므로 1개 경우로 칩니다)
이를 바탕으로 카드 i개에 대하여 점화식을 세워보면 다음과 같습니다.
※i는 카드의 개수, 테이블[i]는 i개 카드를 구매하기 위해 지불할 수 있는 가격. 테이블[i]의 기본값은 입력으로 주어진 i개 카드팩의 가격. j는 1부터 i까지의 수. 테이블[i] = max(현재 테이블[i], 카드팩[i]의 가격, 테이블[i - j] + 테이블[j]) while (j = 1, j <= i) if (j가 i의 약수) 테이블[i] = max(현재 테이블[i], 카드팩[j]의 가격 * (j / i)
테이블은 DP테이블입니다. 입력값 n개로 만들면 되고 코드를 짜보시면 아시겠지만 카드의 최댓값이 1000이라고 공간을 1000으로 만들 필요는 없습니다. 메모리 측면에서 비효율적입니다. 또한 위 식에서 테이블[j]에 대해 발생하는 경우를 따지지 않는 이유는 이미 이전 순회에서 최선의 경우(최댓값을 말합니다)가 적용되었기 때문입니다.
작성 코드 (.py)
import sys
input = sys.stdin.readline
n = int(input())
cards = [0] + list(map(int, input().rstrip().split()))
table = [0] * (n + 1)
for i in range(1, n + 1):
table[i] = cards[i]
for j in range(1, i + 1):
table[i] = max(table[i], table[j] + table[i - j])
if i % j == 0:
table[i] = max(table[i], cards[j] * (i // j))
print(table[n])
작성 코드 (.js)
function solution(n, cards) {
table = Array(n + 1).fill(0);
for (let i = 1; i <= n; i += 1) {
table[i] = cards[i - 1];
for (let j = 1; j <= i; j += 1) {
table[i] = Math.max(table[i], table[j] + table[i - j]);
if (i % j === 0) {
table[i] = Math.max(table[i], cards[j - 1] * parseInt(i / j));
}
}
}
return table[n];
}
solution(10, [1, 100, 160, 1, 1, 1, 1, 1, 1, 1]);