[백준] 11052번 문제 (카드 구매하기) 파이썬(Python) 풀이

 

n = int(input())
dp = [0] * (n + 1)
prices = [0] + list(map(int, input().split()))
dp[1] = prices[1]

for i in range(2, n + 1):
    for j in range(1, i + 1):
        dp[i] = max(dp[i], dp[i - j] + prices[j])

print(dp[n])

문제가 너무 길어서 읽고 이해하는데 시간이 좀 걸린다.

전형적인 dp 문제이며 이중 for문을 통해 풀 수 있었다.

 

카드를 n개 구매하는 경우의 최대 금액을 dp에 index와 숫자를 일치 시켜서 dp에 할당을 해준다.

 

• 카드를 1개 구매하는 경우의 최대 금액은 당연하게도 카드를 1개 구매하는 것이다.
• 카드를 2개 구매하는 경우의 최대 금액은 max(카드 2개가 포함된 팩 1개 구매하는 경우, 카드 1개가 포함된 팩 2개 구매하는 경우)로 나타낼 수 있다.
• 카드를 3개 구매하는 경우의 최대 금액은 max(카드 3개가 포함된 팩 1개 구매하는 경우, 카드 2개가 포함된 팩 1개 + 카드 1개가 포함된 팩 1개를 구매하는 경우, 카드 1개가 포함된 팩 3개 구매하는 경우)로 나타낼 수 있다.

 

이것을 코드로 나타내면 아래와 같이 나타낼 수 있고,

for i in range(2, n + 1):
    for j in range(1, i + 1):
        dp[i] = max(dp[i], dp[i - j] + prices[j])

dp[i]에는 항상 카드를 i 개 사는 경우의 최대 지불 금액이 저장되게 된다.