문제

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

dp[i] 정의

• i 개의 카드를 구매했을 때 최대 가격

점화식

• dp[i] = i개의 카드를 구매할 때 최대 가격
• dp[i-k] = 최적의 방법으로 구매한 가격
• P[k] = k개의 카드를 구매하기 위한 가격

dp[i] = Math.max(dp[i], dp[i-k] + P[k])

• dp[i-k] + P[k] 를 계산하고, 모든 k에 대한 조합의 최대 값을 찾는다.

code

const run = (inputs: string[]) => {
  const [num, string] = inputs;
  const totalQuantity = Number(num);
  const numbers = string.split(' ').map(Number);
  // 키드 개수에 따른 최댓값 저장
  const dp = new Array(totalQuantity + 1).fill(0);

  for (let i = 1; i <= totalQuantity; i++) {
    for (let k = 1; k <= i; k++) {
      // i개 샀을 때의 최댓값 계산
      dp[i] = Math.max(dp[i], dp[i - k] + numbers[k - 1]);
    }
  }

  return dp[totalQuantity];
};

• 구매할 카드 개수만큼 반복
• 카드를 1개 구매 했을 때, 2개 구매 했을 때 … 등에 대한 조합 고려하여 모든 카드 팩 탐색(이중 반복문)
• 시간 복잡도 O(n^2)