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

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

11052번: 카드 구매하기

 

< 소스 코드 >

n = int(input())
cards = list(map(int,input().split()))
# 최대 카드 값 배열 dp
dp = [0]*1001 

for i in range(1,n+1):
  for j in range(1,i+1): # j 개짜리 카드 값은 cards[j-1]
    dp[i] = max(dp[i],dp[i-j]+cards[j-1])
print(dp[n])

 

< 설명 >

위 코드에서, i 개짜리 카드값  Pi 는 cards[i-1] 에 저장되어있고, dp 는 그냥 dp[i] 가 i 개 카드 구매 시 최대값이다.

dp[i] 는 dp[0] + cards[i-1] (Pi) 부터 dp[i-1] + cards[0] ( i-1 개 카드 최대값 + P1)까지의 값들 중 MAX 값이다. 

 

예를 들어, 카드 4개를 구매한다고 했을 때...

P4 ( cards[3] )
1개 구매 시 최대 + P3 ( dp[1] + cards[2] )
2개 구매 시 최대 + P2 ( dp[2] + cards[1] )
3개 구매 시 최대 + P1( dp[3] + cards[0] )

 

를 비교한 최대값이 DP[4] 가 된다.

 

참고.

dp[0] = 0 

dp[1] = cards[0]

dp[2] = max( dp[1] + cards[0], dp[0] + cards[1] )

dp[3] = max( dp[2] + cards[0], dp[1] + cards[1], dp[0] + cards[2] )

dp[4] = max( dp[3] + cards[0], dp[2] + cards[1], dp[1] + cards[2], dp[0] + cards[3] )