백준 11052 파이썬 (카드 구매하기)

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

🧐 점화식 도출

i개의 카드를 구매하기 위한 최대 금액 : dp[i]
k개가 들어있는 카드 팩 : cp[k]
dp[i] = cp[k] + dp[i-k] 가 성립

💻 Code

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

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

print(dp[n])

• 중첩 for문을 사용해서 카드팩 종류의개수만큼 반복

---

➕ 16194 카드 구매하기 2

문제 : https://www.acmicpc.net/problem/16194

💻 Code

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

for i in range(1,n+1):
    dp.append(dp[i-1] + cp[1])
    for k in range(2, i+1):
        dp[i] = min(dp[i], dp[i-k] + cp[k])

print(dp[n])

• 위에 문제와 점화식은 동일
• 그러나 위 문제처럼 0으로 초기화 할경우 최솟값은 0이 고정
• 처음부터 초기화 하는 것이 아닌 append를 활용하여 하나씩 늘렸다. (0 이아닌 false로 초기화 한다음 if문 사용해서 하는 사람도 있더라~)