백준-11052-카드 구매하기

문제

카드 구매하기

풀이

문제조건 해석

N개 카드를 구매하기 위해 지불해야 하는 최댓값 찾기

그리디로 풀면 안된다.

알고리즘

dp[i] : i개 카드 금액의 최댓값

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

\[dp[i] = max(dp[j]+p[i-j]), j는 0부터 i-1까지\]

코드

n = int(input())
p = [int(x) for x in input().split()]

p.insert(0, 0) # 인덱스 맞춰주기 위함
dp = [0 for _ in range(n+1)]
for i in range(1, n+1):
    dp[i] = max([dp[j]+p[i-j] for j in range(i)])
print(dp[n])

배운점

• 처음부터 그리디 / dp 구분은 쉽지 않다. 그리디 먼저 해보고 안되면 dp하자
• dp문제는 일단 항 나열해놓고 규칙 찾는게 가장 빠르다.