[BOJ] 11052 카드 구매하기 (Python / 파이썬)

🧷 문제

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

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구하는 문제이다.

🛠 풀이

이 문제는 Bottom-Up 방식의 다이나믹 프로그래밍(DP)를 이용하여 해결할 수 있다.

Step 1.
 이 문제를 풀기 위해 생각을 해보면 n개의 카드를 구매하기 위한 최대 금액 d[n]은 d[n], d[1] + d[n-1], d[2] + d[n-2], ... , d[j] + d[n-j]중 가장 큰 값과 같다.

Step 2.
 for문을 돌기 전 d[i]의 값을 입력으로 받은 card_pack[i]로 초기화 시켜준 후에 j == 1와 j == i-1은 같으므로 j는 i의 절반까지만 돌도록 한다.

Step 3.
 for문에서 i가 n까지 모두 돌게 되면 n장의 카드를 사는데 지불해야 하난 금액의 최댓값이 d[n]에 저장되어 있기 때문에 출력하면 된다.

🖊 나의 코드

import sys

input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    card_pack = list(map(int, input().split()))
    card_pack.insert(0, 0)

    d = [0] * (n+1)
    d[1] = card_pack[1]

    for i in range(2, n+1):
        d[i] = card_pack[i]
        for j in range(1, i//2 + 1):
            d[i] = max(d[i], d[j]+d[i-j])

    print(d[n])