[백준-11052] 카드 구매하기

문제

링크

코드

import sys
input = sys.stdin.readline

n = int(input())
price = [0] + list(map(int, input().split()))

dp = [0] * (n+1)

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

print(dp[n])

풀이

for i in range(1, n+1) :

카드를 1장, 2장, 3장, ..., n장 샀을 때 최댓값을 구한다.

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

카드를 i장 구매하려고 할 때,
j장짜리 카드팩을 사고, i-j장 카드를 살 수 있다.
그러므로 j장 카드팩의 가격과, i-j장 카드를 샀을 때 최댓값을 더하면 카드 i장의 최댓값이 나온다.

ex)
카드를 3장 구매하려고 할 때 $(i=3)$

$j$	$i - j$
1	2
2	1
3	0

이렇게 모든 경우로 구매했을 때 최댓값을 구할 수 있다.

참고

• [알고리즘] 백준 카드구매하기 11052 DP 최댓값

---

잘 이해가 안돼서 못풀고 계속 이 문제만 볼 수는 없기 때문에 다른 분의 풀이를 봤다.
체크해뒀으니 나중에 다시 풀어보자.

아직 실력이 부족해서 과제에 시간이 너무 많이 소요되다보니 문제를 많이 풀지 못했다ㅠㅠ
꾸준히 풀어야 하는데 제발 한 주 목표 양만큼만 풀자 꼬옥꼬옥