카드 구매하기 실버1 (백준, DP)

N = int(input())
p = [0] + list(map(int,input().split()))
dp = [0 for _ in range(N+1)]


for i in range(1,N+1):
    for k in range(1,i+1):
        dp[i] = max(dp[i], dp[i-k] + p[k])
print(dp[i])

 

작은 문제부터 생각해본다.

 

카드를 한개 사는법부터

dp[i] = 카드 i개 구매하는 최대 가격 , p[k] = k개가 들어있는 카드팩 가격 이라고 했을때

 

4

3 5 15 16 을 예시로 들자.

dp[1] 은 언제나 p[1] 과 동일할 것이므로 3 일 것이다.

dp[2] 는 dp[1] + p[1] 또는 p[2] 둘 중 큰 값일 것이므로 8 이다.

dp[3] 은 dp[1] + p[2] , dp[2] + p[1] , p[3] 중 큰 값일 것이므로 15가 된다.

마지막으로 dp[4] 는 dp[1] + p[3] , dp[2] + p[2] , dp[3] + p[1] , p[4] 중 큰 값이므로 18 이 된다.

 

따라서 점화식은 dp[i] = p[k] + dp[i - k] 가 된다.