11052

날짜 : 2022. 12. 28

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())
num = list(map(int, sys.stdin.readline().split()))
num.insert(0, 0)
dp = [0] * (n + 1)

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

print(dp[n])

 

 

풀이

- dp[i]를 i 개 구매하는 경우의 최대 가격,  num[k]를 카드가 k개 들어가 있는 팩의 가격이라고 가정한다.

- 여기서 i 개의 카드를 최대 가격으로 구매한다면 다음과 같은 비교식이 만들어진다.

1) num[1] + dp[i - 1] : 1개가 들어 있는 카드팩을 구매하고 (i - 1) 개는 이미 뽑은 경우(최고가격으로 뽑음)

2) num[2] + dp[i - 2] : 2개가 들어 있는 카드팩을 구매하고 (i - 2) 개는 이미 뽑은 경우(최고가격으로 뽑음)

3) num[3] + dp[i - 3] : 3개가 들어 있는 카드팩을 구매하고 (i - 3) 개는 이미 뽑은 경우(최고가격으로 뽑음)

...

i) num[i] + dp[i - i] : i개가 들어 있는 카드팩을 구매하고 (i - i) 개는 이미 뽑은 경우(최고가격으로 뽑음)

 

해당 값들을 전부 비교하면서 최댓값으로 갱신 후 dp[n]을 출력한다. 

 

 

알게된 점

- 

 

 

참고 사이트

- https://infinitt.tistory.com/250

백준 (boj) 파이썬 - 11052 번 : 카드 구매하기 (DP)