백준 11052 파이썬 python 카드 구매하기 @@ 황소처럼 우직하게

n = int(input())

dp = [0 for i in range(n + 1)]

p = list(map(int, input().split()))

for i in range(1, n+1):
  cost = 0
  for j in range(1, i):
    sum = dp[j] * (i // j)
    if i % j != 0:
      sum += dp[i - j*(i//j)]
    if sum > cost:
      cost = sum
    
  if cost > p[i - 1]:
    dp[i] = cost
  else:
    dp[i] = p[i - 1]

print(dp[n])
    

자 이것도 다이나믹 하게 풀어야합니다.

다이나믹하게 풀 수 있도록 dp 배열을 만들고요.

n이 주어졌을때,

1개만 사야한다 했을 때, max값은?

2개만 사야한다 했을 때, max값은?

...

n개만 사야한다 했을 때, max값은?

이런식으로 순서대로 dp 배열에 쌓아나갑니다. 그리고 마지막에 dp[n] 을 뱉으면 되겠죠

이제 문제는

각 개수에서 max값을 어떻게 선정할지입니다.

자 간단합니다. 5개를 사야한다 했을 때 max값 구하는 과정 보겠습니다.

dp[1] * 5   ,   dp[2] * 2 + dp[1]   ,   dp[3] + dp[2]   ,   dp[4] + dp[1]   ,   p[4]

(지금 dp는    '인덱스=수'    인 반면에 p 는    '(수-1) = 인덱스'    입니다. p는 인풋값입니다^^)

이 5개 요소중에서 max값 찾으면 됩니다.

5개를 사야한다 했을 때, 1부터 4까지 for문 돌리시는데,

각 수로 일단 dp[j] 값을 최대한 넣고 남는 수가 있다면

남는 수 = k, 만큼 dp[k] 더하시면 됩니다.

 

이만, hjp845 였습니다.

--

며칠뒤에 한번 더 풀어 봤는데요

깔끔하게 푼 코드는 아래글에 있습니다.

백준 11052 파이썬 python : 카드 구매하기 @@황소처럼 우직하게@@n의 입장에서 생각하라