[백준 11052] 카드 구매하기 (Python)

 

하 DP 너무 어렵다 ... 정말루 .. 알고리즘 중에 가장 어려운 것 같다.

계속해서 알고리즘을 짜는데 너무 어려워서 구글링해서 다른 사람의 코드를 참고하였다.

 

일단 기본적으로 1개의 카드를 살 때 최대 금액, 2개 카드 최대 금액, ..., n개의 카드를 살 때 최대 금액 이런식으로 점진적으로 풀어 나가야 한다.

 

점화식부터 찾아보자.

dp는 i 개의 카드를 살때 최대 금액을 저장하는 리스트이고 p는 i개의 카드를 살때 정해진 금액이다.

 

dp[0] = 0

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

dp[2] = max(dp[1] + p[1], dp[0] + p[2])

dp[3] = max(dp[2] + p[1], dp[1] + p[2], dp[0] + p[3])

dp[4] = max(dp[3] + p[1], dp[2] + p[2], dp[1] + p[3], dp[0] + p[4])

 

위 점화식을 기반으로 코드를 작성하였다.

 

내 코드

n = int(input())

cards = list(map(int, input().split()))
cards.insert(0, 0)
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] + cards[j])

print(dp[-1])

dp문제를 풀 때는 항상 점화식을 먼저 찾으려고 노력해야겠다 ..

 

일단 dp문제 마스터하고 소마 코테 결과 나올때까지 sql 정복해보는걸루 ~!! 홧팅 아쟈아쟈

 

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