백준 11052 카드 구매하기 파이썬

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

11052번: 카드 구매하기

카드를 구매하는데 최대한 많은 돈을 써야했던 문제이다.

카드를 각 n장 샀을때 최대값을 dp[n]에 저장해주는 dp배열을 만들었다.

그 후 2중 for문을 사용해 4개를 살때 dp[4]를 dp[3]+s[1] ,dp[2]+s[2],dp[1]+s[3],dp[4]+s[0]인(안의 숫자는 index가 아니라 구매한 카드 숫자의 개수이다.) 경우 중에서 가장 큰 값을 dp[4]로 저장해주면서 우리의 목표인 n장까지 같은 방법으로 구해줬다.

n=int(input())
s = list(map(int,input().split()))
dp =[0]*(n)
for i in range(n):
    dp[i]=s[i]#우선 n장 사는 경우이니 초기값은 s[i]로 해준다.(n(장) = i+1(index))
    for j in range(i):
        dp[i] = max(dp[i],dp[i-j-1]+s[j]) #dp[i-j-1]+ s[j]인 경우가 이해 안 될수 있는데 맨 아래서 설명함
print(dp[-1])
#i = 3 , j =2
#dp[3] = max(dp[3],dp[0]+s[2])dp[3]은 4장의 최댓값 dp[0]은 1장의 최댓값 s[2]는 3장의 가격 
#따라서 dp[0]+s[2]은 4장을 구매하는 경우중 하나이다.