백준 알고리즘[11052]카드 구매하기 python코드

문제 사이트 : https://www.acmicpc.net/problem/11052

생각의 시퀀스

각각 다르거나 같은 개수의 카드가 들어있는 카드팩을 샀을 때, 모든 카드의 합이 N이 되는 경우의 최대값을 구하라.

처음 든 생각은 기계적으로 튀어나온 dp[i] = max(arr[i], dp[i-1]+arr[0])

arr이 카드팩 비용이고 dp는 i-1개의 카드를 산 경우 최대 비용.

그러므로 dp[0] = arr[0]

하지만 위 코드는 동작하지 않았고 나는 멍청했다..

 

위 점화식에서 dp[i-j]+arr[j-1]를 쓴다면 시간 오버가 될거라 생각함.

 

그래서 멀리 돌아돌아 카드팩을 사는 모든 경우의 수를 재귀식으로 돌리고, 카드의 합이 N이 될때마다 max인지 구하는 식으로 생각해봤는데 이게 더 오래걸릴거같음.

그래서 다시 처음으로 돌아와서 점화식 이용함.

코드

마침 pycharm이 켜있길래 python으로 구현함

n = int(input())
arr = input().split()
for i in range(len(arr)):
    arr[i] = int(arr[i])


dp = [0]
#dp[i] = max(p[i], dp[i-1]+p[i])
#일단 카드 팩을 구매할 수 있는 모든 경우의 수 탐색하는 방법을 구상해보자
# n이 1이라면, 1
# n이 2라면, 1+1, 2
# n이 3이라면, 1+1+1, 2+1, 3
# n이 4라면, 1+1+1+1, 2+1+1, 2+2, 3+1, 4
# 이떄 1번 방법이 max일까 2번 방법이 max일까 3번이 max일까 4번이 max일까?
# n<= 1000, p_i= 10000
# ..이랃ㄴ 첨검롱 해본ㅁㅇ
dp[0] = arr[0]
for i in range(1, n):
    max_val = 0
    for j in range(1, i+1):
        max_val = max(max_val, dp[i-j]+arr[j-1])
    dp.append(max(arr[i], max_val))
print(dp[-1])