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

백준 11052번

최종 제출 코드

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

for i in range(1,N+1):
  for k in range(1,i+1):
    dp[i] = max(dp[i], dp[i-k] + p[k])
print(dp[i])

◼ 최대값을 찾기 위해서는 카드팩을 구성하는 숫자의 조합을 모두 고려해야 한다.

• ex) N=5인 경우, 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 1+4, 2+3, 5의 경우를 모두 고려해야 한다.
• 문제의 예시를 들어 그림으로 설명
• dp[i]에는 카드를 i개 살 때의 최적값이 담겨있다.
  

코드 출처