N개의 카드를 구매하기 위해 지불해야 하는 금액의 최솟값 구하기
11052문제와 같은 방식으로 풀수 있다.
- i개의 카드를 사는데 마지막으로 선택한 카드팩은 j개를 가진 카드팩이다.
- i-j개의 카드를 샀을 때는 i-j개를 살 때 지불해야하는 최솟값이다.
- 여기서 j개를 사면 i개의 최솟값이 된다.
따라서 다음과 같은 점화식이 만들어진다.
dp[i] = min(dp[i], dp[i - j] + P[j - 1])16194
Folders and files
| Name | Name | Last commit date | ||
|---|---|---|---|---|
parent directory.. | ||||