[백준] 11052 '카드 구매하기' 파이썬(python)

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

11052번: 카드 구매하기

n = int(input())
p = [0] + list(map(int,input().split()))	# 주어진 갯수에 맞는 가격들을 p라는 리스트로 받는다
dp = [0 for _ in range(n+1)]	# DP 테이블

for i in range(1,n+1):
    for k in range(1,i+1):	# dp[i]의 최댓값 찾기
        dp[i] = max(dp[i], dp[i-k] + p[k])
        
print(dp[n])

Point

• DP를 활용한 알고리즘 문제
• 일단은 귀납식으로 나열을 해본다.

첫번째는 당연히 경우의 수가 아래와 같이 하나밖에 나오지 않는다.

 

dp[1]  = p[1]

 

이후 두번째 최댓값을 구하는 것부터는

 

dp[2] =

dp[1] + p[1] or

dp[0] + p[1]

 

dp[3] =

dp[2] + p[1] or

dp[1] + p[2] or

dp[0] + p[3] 

 

이런 식으로 진행이 된다. 여기서 알수 있듯이 큰 문제를 위해 작은 문제들을 푸는 것이 필요하다. (dp[3]을 구하는 것에는 dp[2]와 dp[1]이 이용된다)

 

따라서 DP를 적용할 수 있으며 이에 따라 DP 테이블을 이용하고, 여기 문제의 패턴을 보면 dp[n]을 구하는 것은 결국 dp[a] + p[b]에서 a+b=n이라는 규칙을 발견할 수 있다. 따라서 이를 점화식으로 dp[k] + p[i-k]로 진행하여 이중포문을 이용해 최댓값을 찾는 방식을 사용하면 된다.

 

결국 두번째 for문은 dp[i]의 최댓값을 찾는 과정이다.