[백준] 11052 - 카드 구매하기 - (python 파이썬)

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

11052번: 카드 구매하기

 

 

풀이과정 :

dp문제 중 줄어드는 숫자가 정확히 제시되어 있지 않은 문제였고, 이해하는데 시간이 걸렸다.

다른 dp문제 문제 처럼 리스트를 만들었고(총 가격, n개당 가격), 그 중에 최대값을 찾기위해

조건문을 사용하여 dp(총 가격)을 갱신해주면서 하나씩 숫자를 채워나가는 코드이다.

 

card_num = int(input())
dp = [0] * (card_num+1) # 전체 가격
prices = [0] + list(map(int, input().split())) #n개당 가격
dp[1] = prices[1] #1개일땐 같고,
dp[2] = max(prices[1]*2, prices[2]) #2개일때 또한 지정해줄 수 있다.

for i in range(3, card_num+1):
    for j in range(1, i+1):
        if dp[i] <= dp[i-j] + prices[j]:
            dp[i] = dp[i-j] + prices[j]  #최대값으로 갱신
print(dp[card_num])

답(이미지)

 

후기: dp문제는 볼때마다 새롭고, 정신없는것 같다... 더 많이 풀어봐야 할것 같다.