11052번: 카드 구매하기 / silver 1 / DP

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

11052번: 카드 구매하기

'''
11052번: 카드 구매하기 / silver 1 / DP
'''
# 1. 카드 개수 n, 카드팩 card 입력 받기
n = int(input())
card = [0]
card += list(map(int, input().split()))
# 2. dp 리스트 만들기 / 카드 i일때, 최댓값 담기
dp = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
    a = i
    b = 0
    while a != 0:
        case = card[a] + dp[b]
        if case > dp[i]:
            dp[i] = case
        a -= 1
        b += 1
# 3. dp[n] 출력 하기
print(dp[-1])

로직은 주석 처리 !

 

코드 리뷰

- 문제를 이해하고 고민하다 DP라고 생각했는데 역시 DP 알고리즘이었다 !!

 

# 2. dp 리스트 만들기 / 카드 i일때, 최댓값 담기

- dp 리스트 / index: 카드개수, value: 금액의 최댓값

- 예를들어 dp[3] = 7이면, 카드 3개를 사야 할 때, 금액의 최댓값 = 7