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

문제 

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

코드 

import sys
input = lambda : sys.stdin.readline().strip()

n = int(input())
p = [0] + list(map(int, input().split()))
dp = [0 for _ in range(n+1)]

for i in range(1, n+1):
    for k in range(1, i+1):
        # dp를 max값으로 계속 갱신
        dp[i] = max(p[k] + dp[i-k], dp[i])

print(dp[n])

 

풀이 

사실 처음에는 접근이 어려워서 힌트를 보고 풀었다🤔

 

점화식을 찾고 그 점화식에 맞는 코드를 짜서 풀 수 있었다. 

문제에 있는 예시로 설명하자면, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 

dp[1] == 1 

dp[2] == (k=1일 때) max(1 + 1, 0) == 2

             (k=2일 때) max(5 + 0, 2) == 5

dp[3] == (k=1일 때) max(1 + 5, 0) == 6

             (k=2일 때) max(5 + 1, 6) == 6

             (k=3일 때) max(6 + 0, 6) == 6

       

이렇게 점화식을 따라서 더하다 보면 각 dp[i]에는 더해서 i가 되는 최댓값들이 저장되고, 마지막 dp[i]를 구할 때도 최대 합으로만 만들어진 리스트에서 뽑는 것이므로 항상 최댓값이 나온다.