[백준 11052 카드 구매하기] - 파이썬 풀이 🦄

• 백준 11052 카드 구매하기 - 파이썬 풀이 🦄
  • 문제
  • Keypoints
  • Solution
  • References

백준 11052 카드 구매하기 - 파이썬 풀이 🦄

문제

N개의 카드 가격이 있을 때, N개를 지불하는데 사용되는 최대금액을 찾는 문제

Keypoints

• 1,2,3,4, ... 순서대로 DP에 최대값을 저장한다.
• K번째에서는 이중 for문의 index i에 대해서 합이 K= (i +K-i)이 되는 모든 i를 고려한다.

Solution

num_cards = int(input())
prices = list(map(int, input().split()))

max_store_by_num = [p for p in prices]  # 0 index is 1 number of card
for i in range(1, num_cards):
    for j in range(0, i):
        partA, partB = max_store_by_num[j], max_store_by_num[i-j-1]
        max_store_by_num[i] = max(max_store_by_num[i], partA+partB)
print(max_store_by_num[-1])

References

Problem Link