다이나믹 프로그래밍 공부를 시작하는 문제이다. 규칙을 찾아 점화식을 만드는 것이 중요했다. 우선 메모라이제이션을 위한 배열 dp를 만들고 dp의 인덱스는 구매하는 카드의 수로 두고 문제를 접근하였다. dp에 몇장의 카드를 살 때의 최대 금액을 저장하여 dp[n]을 결과값으로 내는 방식으로 해결하였다.

• dp[1]이라면 카드를 1장 사는 경우의 수이므로 p[1]이다.
  dp[1]=dp[0]+p[1]=p[1]
• dp[2]라면 카드를 1장 사는 경우인 dp[1]과 p[1]의 합 과 카드를 0장 산 경우인 dp[0]과 p[2]의 합 중 큰 값을 취한다.
  dp[2]=max(dp[1]+p[1], dp[0]+p[2])
• dp[3]이라면 카드를 2장 사는 경우인 dp[2]과 p[1]의 합과 카드를 1장 사는 경우인 dp[1]와 p[2]의 합 과 카드를 0장 사는 경우인 dp[0]과 p[3]의 합 중 큰 값을 취한다.
  dp[3]=max(dp[2]+p[1], dp[1]+p[2], dp[0]+p[3])

이러한 과정을 식으로 나타낸다면 다음과 같이 나타낼 수 있다.

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

dp에 각 카드 수 별 최대 금액을 저장하고 더 많은 카드를 살 때에 dp에 저장된 수를 그대로 사용하여 연산의 크기를 줄이게 된다.

• n을 입력받는다.
• 카드팩의 정보를 입력받는 배열 p를 선언하고 앞에 [0]을 붙여 인덱스 1부터 입력받도록한다.
• 인덱스별 최대 금액을 저장할 배열 dp를 0 n+1개로 구성한다.
• dp[1]은 dp[0]+p[1]이므로 p[1]으로 갱신한다.
• 2부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> 1부터 i까지 반복하는 j에 대한 for문을 돌린다.
  --> 만약 dp[i]가 dp[i-j]+p[j]보다 작다면 dp[i]를 dp[i-j]+p[j]로 갱신한다. (최대 금액을 구하는 과정)
• dp[n]을 출력한다.

Code

n=int(input())
p=[0]+list(map(int, input().split()))
dp=[0]*(n+1)
dp[1]=p[1]
for i in range(2, n+1):
    for j in range(1, i+1):
        if dp[i]<dp[i-j]+p[j]:
            dp[i]=dp[i-j]+p[j]
print(dp[n])