Search

[백준 11052] 카드 구매하기

[백준 11052] 카드 구매하기

Tip

다이나믹 프로그래밍
Dn = 카드 N개의 최대 지불 금액
카드 갯수의 모든 경우에 대해 (N = 1, 2, 3....N)
보톰업 방식(상향식)으로 지불에 필요한 최댓값 구하기
점화식 세우기
N = 4
P₁ = 1, P₂ = 5, P₃ = 6, P₄ = 7
D₀ = 0
D₄
D₃ + P₁ → D₄₋₁ + P₁
D₂ + P₂ → D₄₋₂ + P₂
D₁ + P₃ → D₄₋₃ + P₃
D₀ + P₄ → D₄₋₄ + P₄
Dn = max(Dn₋₁ + P₁, Dn₋₂ + P₂, ... , Dn₋n + Pn)
코드로 구현
# 이중 반복문 사용 # D[1]부터 차례대로 구해 최종적으로 D[n]을 구하는 방식 for i in range(1, n + 1): # 1 ~ n for j in range(1, i + 1): # 1 ~ i d[i] = max(d[i], d[i - j] + p[j])
Python

풀이 소스 코드

import sys si = sys.stdin.readline # 구입하고자 하는 카드개수 n 입력 n = int(si()) # 카드팩 가격 입력 # 1번 인덱스부터 사용하기 위해 p = [0] + list(map(int, si().split())) # DP 테이블 -> 카드 갯수에 따른 지불 최댓값을 저장 d = [0] * (n + 1) # 인덱스의 범위 : 1 ~ n # 보톰업 DP for i in range(1, n + 1): # 1 ~ n for j in range(1, i + 1): # 1 ~ i d[i] = max(d[i], d[i - j] + p[j]) print(d[n])
Python