[Python] 백준 11052번 카드 구매하기(DP)

문제

풀이

dp 문제이다.

만약 카드 3개를 산다면 사는 방법은 카드 3개 짜리 팩 1개, 카드 2개 짜리 팩 1개와 한 개 짜리 팩 한 개, 한 개 짜리 팩 3개 가 있다.

하지만 2개를 살 때에 최댓값이 1개 짜리 팩을 두 개 사는 것이 더 많을 경우, 카드 2개 짜리 팩을 사는 경우의 수가 줄어 든다. 따라서 카드 3개를 사는 경우의 수는 2가지가 된다.

정리해 보면 항상 최댓값을 저장하면서 cache를 쌓아 가면, 4개일 경우, 시그마 k=1부터 4 까지 합 이 시간 복잡도가 된다.

n의 범위가 1000 이하 이니, 대략 n(n+1)/2, 1000(1000+1)/2=500,500 5십만 5백이 된다. 따라서 내가 생각하는 최대 계산 수 1억 보다는 현저히 적다.

n = int(input())

arr = list(map(int, input().split()))

arr.insert(0, 0)

cache = [0 for _ in range(n+1)]

for i in range(1, n+1):

    for j in range(1, i+1):

        cache[i] = max(cache[i-j]+arr[j], cache[i])

print(cache[-1])