11052. 카드 구매하기

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

11052번: 카드 구매하기

 

d[n]: 카드 n장을 구매할때의 최대 비용

d[1]: 카드 1장을 구매할때의 최대 비용

d[2]: 카드 2장을 구매할때의 최대 비용

d[4]: 카드 4장을 구매할때의 최대 비용...

 

그렇다면 예제처럼 4장을 구매할 때의 경우를 살펴보면

1. d[0] + 4장을 한번에 구매하는 비용 p[4]

2. d[1] + 3장을 한번에 구매하는 비용 p[3]

3. d[2] + 2장을 한번에 구매하는 비용 p[2]

4. d[3] + 1장을 한번에 구매하는 비용 p[1]

 

d[4]는 1,2,3,4번 중 최댓값이라고 할 수 있다.

 

 

예제에서 p1 = 1, p2 = 5, p3 = 6, p4 = 7

 

d[0]은 카드 0장을 구매하는 최대 비용 = 0

d[0] = 0

 

d[1]은 카드 1장을 구매하는 최대 비용 즉 그냥 p[1]이다. 

d[1] = 1

 

d[2] 

1장을 구매하는 최대비용(d[1]) + 그냥 1장 구매(p[1]) : 1 + 1 = 2

0장을 구매하는 최대비용(d[0]) + 그냥 2장 구매(p[2]) : 0 + 5 = 5

둘 중 큰 값은 5이므로, d[2] = 5

 

d[3]

2장을 구매하는 최대비용(d[2]) + 그냥 1장 구매(p[1]) : 5 + 1 = 6

1장을 구매하는 최대비용(d[1]) + 그냥 2장 구매(p[2]) : 1 + 5 = 6

0장을 구매하는 최대비용(d[0]) + 그냥 3장 구매(p[3]) : 0 + 6 = 6

최대값은 6이므로, d[3] = 6

 

1. d[0] + p[4] = 7

2. d[1] + p[3] = 7

3. d[2] + p[2] = 10

4. d[3] + p[1] = 7

최대값은 10이므로 d[4] = 10

 

bottom-up

d = [0] * 1001

n = int(input())
p = input().split()

for i in range(n): p[i] = int(p[i])

for i in range(1, n+1):
    for j in range(1, i+1):
        d[i] = max(d[i], d[i-j] + p[j-1])

print(d[n])