11052번 : 카드 구매하기 - Python

문제

https://www.acmicpc.net/problem/11052

풀이

카드의 개수에 따른 최대 금액계산을 n개까지 하면 된다.

P[1] = 1, P[2] = 5, P[3] = 6, P[4] = 7을 예로 들어보면

1개를 구매할때는 P[1]을 사면 된다.
dp[1] = P[1]

2개를 구매할때는 P[1] + P[1] 혹은 P[2]의 경우가 있다. 그 중 큰방법으로 구매하면 된다.
dp[2] = P[1] + P[1] or P[2]
-> P[1] + dp[1] or P[2] + dp[0] 이렇게 dp로 바꾼 이유는 경우의 수 중에서 1개 들어있는 팩을 사고, 1개를 더 살때 최대 값으로 사기 위해서 이다.
여기서는 1개이기때문에 그렇지만 3개로 가면 dp[2] + P[1] 이렇게 표현하게 된다. 그러면 1개가 들어있는 팩하고 2개를 더 사야할때 2개를 사는 경우가 2개 들어있는 팩을 사는 경우 or 1개 들어있는 팩을 2개사는 경우가 있기 때문에 그중 더 비싼방법으로 사기 위해서 P[2]가 아닌 dp[2]를 더하는 것이다.

3개를 구매할때는
dp[3] = dp[2] + P[1] or dp[1] + P[2] or dp[0] + P[3]

4개를 구매할때는
dp[4] = dp[3] + P[1] or dp[2] +P[2] or dp[1] + P[3] or dp[0] + P[4]

코드

from sys import stdin, stdout

input = stdin.readline 

n = int(input())

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

for i in range(1, n+1):
    for j in range(1, i+1):
        dp[i] = max(dp[i], p[j]+dp[i-j])

print(dp[n])