문제

카드 구매하기

풀이

이 문제를 처음은 브루트 포스로 무지성으로 풀었는데, 역시 틀렸다
인덱스 자체가 수량을 말하는 것이므로 카드 배열 arr[1] 의 경우 한개를 살때의 금액을 말하는 것이다

이것을 dp배열에는 인덱스 갯수를 살때 가장 많은 금액을 저장한다고 생각한다. 그렇다면 마지막엔 dp[n] 을 출력할때 가장 큰 n개를 가지는 값을 알 수 있을것이다
점화식은 다음과 같이 구현한다

dp[i] = Math.max(dp[i], arr[i] + dp[n - i]); 

해당 점화식의 뜻은 i개의 가장많은 금액을 저장하는 값을 갱신하기 위해
i개의 카드의 값과 나머지 n - i개를 살때의 저장된 값의 합과 비교 한다.

솔직히 dp로 구현하는 방법은 어렵지 않은데, dp라는 생각을 바로 할 수 있었으면 풀었을것같다.

전체 코드

전체 코드