[백준] 11052 - 카드 구매하기 (Python)

문제 출처:

www.acmicpc.net/problem/11052

11052번: 카드 구매하기

문제 풀이 :

• 점화식을 DP[i] = i개를 샀을때 최대비용 으로 잡고 풀었다.
• 점화식을 이용하면 
  DP[i] = max(DP[i-1] +P[1] , DP[i-2]+P[2] , .... ,   DP[i-i] + P[i]) 까지를 고르면 된다. (필자는 다이나믹 프로그래밍을 풀 때 최대한 다른사람에게 미루기 전법을 쓰는데 이게 그 전법이다. DP[i] 이전의 것들이 다 구해졋다고 생각했을때 DP[i]만 생각하는 방법)
• 카드의 가격 자체로 DP를 갱신하는 방법도 있는데 이런 경우에 종류 2가지의 조합에 대해서 신경써야한다.
  예를들어 5장을 살때 3개짜리 팩 + 1개짜리팩 2개 도 되지만 3개짜리팩 + 2개짜리팩 1개도 되기 때문에 이 부분을 신경쓰지 않으면 틀린다.

n= int(input())
p_arr = list(map(int,input().split()))

dp =[0]*(n+1)
p_arr = [0] + p_arr

dp[1] = p_arr[1]
dp[2] = max(p_arr[2] , dp[1]*2)

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

print(dp[n])