11052 카드 구매하기

www.acmicpc.net/problem/11052

11052번: 카드 구매하기

 

아주 단순한 dp문제이다. 하지만 기억이 나지 않는다면 틀릴 수 밖에 없다.

dp[i]를 i개의 카드를 구매할 때 지불할 수 있는 최대 비용이라고 정의한다면

 

1인경우에는

1 뿐이므로 dp[1] = cardPack[1] 일 것이고

 

2인경우에는

1+1, 2

3인 경우에는

1+1+1, 2+1, 3

4인 경우에는

1+1+1+1, 2+1+1, 2+2, 3+1, 4

5인 경우에는

1+1+1+1+1, 2+1+1+1, 2+2+1, 2+3, 3+1+1, 3+2, 4+1, 5

 

의 경우의 수가 있다.

 

이런 규칙의 점화식은 

cardPack[i]과 dp[i-j]+cardPack[j], dp[i] 이렇게 3가지를 비교하여 최대값을 넣어주는 점화식으로 풀 수 있다.

 

이런 유형이 많은 편이므로 외워두는 것이 좋다고 생각한다. 점화식을 세울 수 있는 사고력이면 더 좋다.

 

즉 N개의 카드팩을 1개 고르거나, j개가 들어있는 카드팩을 고르기전 최대값을 고르는 문제로 세분화한다는 아이디어가 필요하다.

 

import sys
input = sys.stdin.readline

n = int(input())

cardPack = dict()
for i,v in enumerate(map(int, input().rstrip().split(" "))):
  cardPack[i+1] = v

# dp[i]는 i개의 카드를 산다했을때 가장 많이 지불할 수 있는 가격
dp = [0] * (n+1)


dp[1] = cardPack[1]

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

print(dp[n])