[#11052] 카드 구매하기

❓ Question

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

📖 Before Start

오랜만에 풀어보는 동적 프로그래밍 문제다.

이번 문제는 동적 프로그래밍 (DP) 을 통해 구매 가격의 최댓값을 구해야 했다.
처음 점화식은 정말 잘 작성했지만, 이를 코드로 어떻게 구현해야 할지가 고민이었다.

✒️ Design Algorithm

동적 프로그래밍을 잘 풀기 위해서는 점화식 설계가 중요하다.

현재 N개 의 카드가 담긴 카드팩의 가격이 1 부터 N 개까지 존재한다.
이 카드팩들을 적절히 잘 담아서 구매 가격의 최댓값 을 구해야 하는 문제인데,
보통 최댓값을 구하라는 문제는 동적 프로그래밍 문제일 확률이 높다.

dp[i]는 i 개의 카드를 구매할 경우 지불할 수 있는 금액의 최댓값 이다.
따라서 점화식은 dp[i] = max(dp[i-1] + P[1], dp[i-2] + P[2], ..., P[i]) 이다.

1. i = 1 or 2 인 경우 별도의 과정을 통해 메모이제이션에 값을 추가해준다.
2. 그 후 i >= 3 부터는 설계한 점화식을 토대로 메모이제이션에 값을 추가한다.

💻 Making Own Code

✅ Correct Code

import sys

read = sys.stdin.readline
N = int(read())
P = [0] + list(map(int, read().split()))
dp = [0] * (N + 1)

dp[1] = P[1]
dp[2] = max(dp[1] + P[1], P[2])

# 점화식 : dp[i] = max(dp[i-1] + P[1], dp[i-2] + P[2], ..., P[i])
for i in range(3, N + 1):
    # dp[i-j] + P[j] 를 반복하여 가장 큰 값을 메모이제이션에 추가.
    for j in range(1, i + 1):
        dp[i] = max(dp[i], dp[i-j] + P[j])
        
print(dp[N])

설계한 점화식을 어떻게 코드로 작성해야 할지에 대해서 고민이 많았다.
따라서 이중 반복문을 통해 공통된 변수 j 를 놓고 max() 함수를 통해 최댓값을 비교하였다.

처음에는 점화식을 잘못 설계해서 틀렸다가 다시 맞췄다.

📖 Conclusion

📒 github Code link

https://github.com/RookieAND/BaekJoonCode/tree/main/%EB%B0%B1%EC%A4%80/Silver/11052.%E2%80%85%EC%B9%B4%EB%93%9C%E2%80%85%EA%B5%AC%EB%A7%A4%ED%95%98%EA%B8%B0

동적 프로그래밍 의 꽃은 역시 점화식 설계 라는 것을 다시금 느꼈다.
꾸준히 다양한 문제를 풀이하면서 실력을 점차 늘려나가는 것이 중요하다.