[CodingTest] BOJ11052 카드 구매하기 ( DP ) With Python

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

11052번: 카드 구매하기

 
 
◎ 문제풀이
 
카드팩 안에는 1 ~ N개의 카드가 들어있다. 카드팩의 비용은 개수에 상관없이 제각각이다. 민규가 N개의 카드를 구할 수 있는 비용의 최댓값을 구하는 문제이다. 
 
N개 목표가 주어졌고
1~N개가 카드팩으로 묶여 있으므로 기저조건이다. 
 
기저조건으로 목표를 구하는 문제이므로 DP로 풀면된다. 
 

 
 
4개의 카드의 최댓값을 구해보자. 4개의 카드를 구할 수 있는 사건은 4개가 있다.
 
첫번째 사건 : 1개 팩 비용 + 3개의 최댓값
두번째 사건 : 2개 팩 비용 + 2개의 최댓값
세번째 사건 : 3개 팩 비용 + 1개의 최댓값
네번째 사건  : 4개 팩 비용 
 
네 가지 사건 중 가장 최대인 값을 구하면 된다. 
 

◎ 코드

import sys 
input = sys.stdin.readline

n = int(input())
pack = [0] #팩
pack.extend(list(map(int,input().split()))) 

d= [0]*1001
d[1] = pack[1]

#BOTTOM-UP방식으로 최대비용 구하기 
for i in range(2,n+1) :
  d[i] = pack[i] # N가지 사건 중 최댓값 구하기
  for j in range(1,i) :
    d[i] = max(d[i],d[i-j] + pack[j])

#출력
print(d[n])