[baekjoon] 백준 11052번(파이썬): 카드 구매하기

문제

11052번: 카드 구매하기

알고리즘

- 반복문을 통해 각 카드 개수의 지불하는 최대 금액을 구한다.

- 각 카드의 개수의 지불하는 최대 금액과 이전의 카드를 지불한 최대 금액 + 현재 카드팩 가격을 비교한다.

예를 들어, 예제 입력 1을 예시로 두어 코드를 수행하면 다음과 같다.

dp[1] = p[1]

dp[2] = dp[1] + p[1] or dp[0] + p[2]

dp[3] = dp[2] + p[1] or dp[1] + p[2] or dp[0] + p[3]

dp[4] = dp[3] + p[1] or dp[2] + p[2] or dp[1] + p[3] or dp[0] + p[4]

코드

import sys


n = int(sys.stdin.readline())
p = [0] + list(map(int, sys.stdin.readline().split()))
dp = [0] * (n + 1)

# 반복문을 통해 각 카드 개수의 지불하는 최대 금액을 구한다.
for i in range(1, n + 1):
    for j in range(1, i + 1):

        # 현재 카드를 지불하는 최대 금액과 이전의 카드를 지불한(i - j) 최대 금액 + j개가 들어있는 카드팩 가격을 비교
        dp[i] = max(dp[i], dp[i - j] + p[j])

print(dp[n])

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법