BaekJoon Online Judge 11052번 파이썬

문제 링크
https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

민규가 원하는 카드의 개수를 card_need 변수로 받았다.
카드팩의 가격을 pack으로 받았다. 그리고 카드팩의 카드 개수와 인덱스를 맞추기 위해 0의 자리에 0을 넣어두고 input을 받았다.

처음에 잘못 짠 코드

card_need = int(input())
pack = [0] + list(map(int,input().split()))

for i in range(1,card_need+1):
  if card_need % i == 0:
    dp_single[i] = pack[i] * (card_need//i)

dp_combination = [0] * (card_need+1)
card_remain = [0] * (card_need+1)

for i in range(1,card_need+1):
  if card_need - i != 0:
    card_remain[i] = card_need - i
    dp_combination[i] = pack[card_remain[i]] + pack[i] 

dp = [0] * (card_need * 2) 
dp = dp_single + dp_combination
print(max(dp))

처음에는 한가지의 카드팩을 원하는 카드의 개수만큼 사는 경우와 여러가지의 카드팩을 원하는 카드의 개수만큼 사는 경우로 나누어 최댓값을 구하는 방식으로 진행했다.
이 방식으로 하다보니 3가지 이상의 카드팩을 구매하는 경우를 구현하기 힘들어서 다른 경우를 생각하게 되었다.

카드 1장만 사려고 할 때, dp[1] = pack[1] 은 무조건 성립이 된다.
그 뒤로는,
dp[2] = max(dp[2], dp[1]+pack[2])
dp[3] = max(dp[3], dp[2]+pack[3])
dp[4] = max(dp[4], dp[3]+pack[4])
…
이렇게 모든 경우의 수를 생각하며 문제를 풀어야한다.

정답 코드

card_need = int(input())
pack = [0] + list(map(int,input().split()))

dp = [0] * (card_need+1)
dp[1] = pack[1]

for i in range(2, card_need+1):
  for j in range(1, i+1):
    dp[i] = max(dp[i],dp[i-j]+pack[j])
    
print(dp[i])