[알고리즘/DP] 11052번 : 카드 구매하기 - python

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

11052번: 카드 구매하기

 

 

---

• 문제
• 소요시간: 27분

---

• 설계하기(접근방법) 

1. 입력받기

 

카드 팩 리스트를 입력받는다

 

2. 구현하기

이전에 풀었던 DP 문제와 유사하다

중복되는 조합이 있으면

 

가장 작은 케이스부터 dp를 처리하고

가장 큰 숫자를 마지막으로 dp를 처리하여

 

카드 수를 뽑을 때 최대값을 구한다

 

3. 출력하기

최대값을 출력한다

 

 

---

• 코드(출력)

n = int(input())
pack = list(map(int, input().split()))
dp = [0] * (n+1)
card = [0] *(n+1)
for i in range(n):
    card[i + 1] = pack[i]

for i in range(1, n+1):
    card_now = card[i]
    for j in range(i, n + 1):
        if dp[j] < dp[j - i] + card_now:
            dp[j] = dp[j - i] + card_now

print(dp[n])

---

• 얻어갈 부분

1. 이전에 풀어봤던 문제와 유사했다