# Purchase Card

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

![](https://3269900549-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MIbwNq54Ge4eqsziHM7%2F-MlPhx3BHTT-ncdWsMsa%2F-MlPirvVyrWMadXpBVUY%2FScreen%20Shot%202021-10-07%20at%209.29.44%20PM.png?alt=media\&token=3daf3fc9-1b06-4386-be2a-f66fc72503f2)

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])**