[BOJ_11052] 카드 구매하기

가장 첫번째 예시를 보면 1을 네 장 사서 4가 되는 것 보다 두장 짜리를 두 번 사서 4를 만드는 것이 4 < 5 * 2 로 금액이 더 큰 것을 알 수 있습니다.

 

작은 문제로 나눠서 생각하는 것이 중요합니다.

예를 들어 세번째 카드를 구매하면 N개 중 3이 소모되는 것 입니다.

그러면 나머지 N-3개에 대한 dp를 출력하면 됩니다.

 

dp를 갱신시켜나가는데 현재카드와 [N-현재카드의 번호]의 dp값을 비교해서 더 큰 것으로 갱신시키면 됩니다.

n = int(input())
card = list(map(int, input().split()))
card.insert(0, 0)
dp = [0 for _ in range(n+1)]

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

print(dp[n])

 

www.acmicpc.net/problem/11052

11052번: 카드 구매하기