Purchase Card

d[n] = n개 카드 구매할 때 지불하는 최대 금액

d[n] 을 구할 때, P[n]과 "다른 값"들을 비교해서 최댓값을 구한다는 것은 알겠는데, 이 "다른 값"을 어떻게 수식으로 나타낼지 몰랐었다.

이 부분을 구체화하자면, d[n] = n개 카드 구매 시 지불 최대 금액, 카드 n개를 구매하는 방법은

• 카드 1개 든 카드패 구매, 카드 n-1개 구매 = P[1] + d[n-1] = 카드 1개든 카드팩 구매 + 카드 n-1개 구매시 지불 최대 금액

• 카드 2개 든 카드팩 구매, 카드 n-2개 구매

• ...

• 카드 n개 든 카드팩 구매, 카드 0개 구매

이런 식으로 카드 i개를 구매함에 따라 추가적으로 구매할 카드 갯수는 달라지기 때문에 나머지는 그냥 N-i개 카드를 구매하는 것으로 치부하면 된다.

따라서 위의 시뮬레이션을 통해 d[n] = max(p[i] + d[n-i]) 라는 식이 나온다!! 여기서 d[n-i] 의 n-i는 0이 최소이기 때문에 반복문을 구현할 때, i가 증가하는 범위는 이 표현식에서의 n까지. 반복 변수로 치환해보면 n=>i, i=>j 이고, j는 i와 같아질 때까지만 증가한다.

d[i] = Math.max(p[ j ] + d[i -j], d[i])