백준 11052번 카드 구매하기 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 11052 카드 구매하기

11052 카드 구매하기

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

11052번: 카드 구매하기

이번 문제의 핵심은 n장의 카드를 구매하는데 가장 많은 돈(최대 값)을 사용해야 한다는 점이다. 문제를 이해하는 것은 오래 걸리지 않았지만 점화식을 어떤 방식으로 만들어야 하는지 이해하는데 오래 걸렸다.

---

코드

import sys
input = sys.stdin.readline

n = int(input())
p = [0] + list(map(int, input().split()))
dp = [0 for _ in range(n+1)]

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

---

풀이

DP를 이용해서 n장의 카드를 구매하는데 각 값들을 비교하여 최댓값을 뽑아내는 문제로 카드의 가격을 저장하는 p와 값을 비교하는 dp를 선언하고 for문으로 진입한다. 위의 정리와 같이 dp[n]은 n장의 카드를 뽑는 최대 값이고 dp[1], dp[2], dp[3]... dp[n+1]을 구해서 dp에 값에 저장한다.

dp[1] = p[1]

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

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

. . .

dp[n] = dp[i-j] + p[j]

두 개의 for문으로 위와 같은 점화식을 작성할 수 있다. i가 3이면 j = [1, 2, 3]으로 이전 dp값들과 p를 더하고 max 내장 함수를 이용하여 큰  dp 리스트를 완성한다.

---

풀이 결과

11052 풀이 결과