백준 11052 파이썬(DP)

DP문제다

DP문제의 가장 큰 특징은 중복되는 서브문제(overlapping subproblem)와 최적 부분 구조(optimal substructure)로 이런 유형의 문제에 접근하기 위해서는 하나의 문제를 작은 그러나 같은 방법으로 풀 수 있는 문제로 쪼개야한다.

 

이번 문제에서는 원하는 카드의 개수를 만드는 최대값을 구해야한다.

카드 1개 샀을때 최대값

카드 2개 샀을때 최대값

카드 3개 샀을때 최대값

카드 4개 샀을때 최대값

이런식으로 생각을 해보면

 

카드 1개 ->  P[1] (=1개 카드 값)

카드 2개 -> max(P[1]+P[1] , P[2])

카드 3개 -> max(P[1]+P[1]+P[1] , P[1]+P[2]  , P[3])

...

 

이런식으로 모두 따져봐야 하는 문제다.

 

#11052번: 카드 구매하기

N = int(input())
P = [0] + list(map(int,input().split()))
d = [0] * (N+1)
d[1] = P[1]

for i in range(2,N+1):
    for j in range(1,i+1):
        if d[i] < d[i-j] + P[j]:
            d[i] = d[i-j] + P[j]

print(d[N])