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

철웅·2023년 2월 10일
0

BOJ

목록 보기
27/46

문제 : 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문 사용해서 하는 사람도 있더라~)

0개의 댓글