[Python] 백준 11052, 16194 카드구매하기 1, 2

코드 작성

n = int(input())
k = [0] + list(map(int, input().split()))  #2
for i in range(1, n+1):
    for j in range(1, i+1):
        k[i] = max(k[i], k[i-j] + k[j])  #1
print(k[n])

코드  풀이

#1

주어진 카드를 n개라고 했을 때 제일 마지막 카드는 n번째 카드라고 할 수 있으며, i번째 카드라고도 할 수 있다.

그렇다면 i번째를 제외한 카드는 n-1개의 카드라고 할 수 있을 것이다.

구하려는 값은 n번재의 최소값이므로

k[i] = max(k[i], k[i-j] + k[j])

라고 작성할 수 있을 것이다.

#2

카드 값은 첫 번재부터 시작하고 파이썬의 인덱스는 0부터 시작하기 때문에 초기값을 넣었다.

#3

11052는 최댓값 문제이므로 max

16194는 최솟값 문제이므로 min으로 작성하면 끝~