[알고리즘] 백준 11052 카드 구매하기

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

다이나믹 프로그래밍 문제를 꽤 많이 풀었음에도, 다른 유형에 비해 적응하기가 어렵다고 느끼고 있다.
그래서 간단한 문제에서 점화식을 도출하는 과정을 글로 정리해보려 한다.

문제는 N개의 카드와 P1, P2, P3, ... Pn를 주어준다 Pn = k는 i장의 카드를 k원에 구입할 수 있음을 의미한다.

그리고 N장의 카드를 구매할 때의 최대 금액을 구해야한다.

1. memoization의 대상이 될 dp 테이블 정의

이 문제에서 구해야하는 것은 카드 N개를 구매했을때의 최댓값이다. 그러므로 dp[i]는 i장의 카드를 구매했을 때의 지불할 수 있는 최대 비용으로 정의한다.

2. 점화식 도출

dp 테이블을 정의했다면, 구현에 필요한 점화식을 도출해야한다. 점화식은 앞서 정의한 dp 테이블 개념으로부터 도출 가능하다.
dp[i]는 i장의 카드를 구매했을때의 최대값이고, 이는 다음과 같은 경우의 수를 고려해볼 수 있다.
dp[i] = max(dp[i-1] + values[1], dp[i-2] + values[2], dp[i-3] + values[3], ... dp[i] + dp[0])

이 식이 의미하는 바를 말로 풀어보면 다음과 같다.
i가 4라고 가정하자.
4장의 카드를 구매할 수 있는 경우의 수는 아래와 같다.

• 3장을 구매하고 1장을 구매하는 비용을 추가로 지불할 경우
  • dp[4-1] + values[1]
• 2장을 구매하고 2장을 구매하는 비용을 추가로 지불할
  • dp[4-2] + values[2]
• 1장을 구매하고 3장을 구매하는 비용을 추가로 지불할 경우
  • dp[4-3] + values[1]

그리고 이 경우의 수들 중에서 최댓값을 dp[4]에 넣어주면 되는것이다.

이를 코드로 표현하면 아래와 같다.

import sys

N = int(sys.stdin.readline())

values = [0] + list(map(int, sys.stdin.readline().split()))
dp = [0 for _ in range(N+1) ]

# 카드 장수(N)에 대하여 반복문 수행
for i in range(1, N+1):
	# 탐색중인 N전까지 반복을 수행한다. 
    # N장을 뽑는 경우를 고려하고 있는데, N+1을 고려하는것은 올바르지 않으므로..
    for j in range(1, i+1):
    	# 각 반복문마다 최댓값에 대해서 dp[i]를 갱신해준다.
        dp[i] = max(dp[i], dp[i-j] + values[j])

print(dp[N])

dp 테이블 도출과 점화식을 도출하는 사고 과정을 더 훈련할 필요를 느끼고 있다..