[BOJ/백준] 11052 카드 구매하기

n=int(input())
card=[0]
card+=list(map(int,input().split()))
dp=[0]*(n+1)

dp[1]=card[1]
dp[2]=max((card[2],card[1]*2))

for i in range(3,n+1):
    dp[i]=card[i]
    for j in range(1,i//2+1):
        dp[i]=max(dp[i],dp[j]+dp[i-j])


print(dp[n])

초창기에 풀었던 문제이다. 

 

현재 DP에서의 초기값을 넣어주고, 두개를 더해서 i가 되는 경우를 갱신해주면 된다.

 

J의 range(i//2+1)인 이유는 중간까지 하면, 그 다음부터는 앞의것의 반복이기 때문이다.