[python/백준] 11052 : 카드 구매하기
문제
풀이
모든 카드팩의 가격을 비교해 최댓값을 찾아야 한다 == DP이다.
<Example>
n = 5
p = [1,4,2,7,3]
DP[A] = B
A장의 카드를 사는데 지불해야하는 최대 금액이 B원이다.
카드 1장 사는데 지불해야하는 최대 금액은 1원
DP[1] = max(P[1]) = 1
카드 2장 사는데 지불해야하는 최대 금액은 4원
DP[2] = max(P[2] , P[1] * 2) = 4
= max(2장 들어있는 카드팩 하나 사는 금액, 1장 카드팩 사는 금액 + 1장 카드 사는 최대 금액)
= max(P[2], DP[1]+P[1])
카드 3장 사는데 지불해야하는 최대 금액은
DP[3] = max(P[3], P[2]*1 + P[1], P[1]*3) = 5원
= max(3장 들어있는 카드팩 하나 사는 금액,\
2장 들어있는 카드팩 하나 사는 금액 + 1장 카드 사는 최대 금액,
1장 들어있는 카드팩 하나 사는 금액 + 2장 카드 사는 최대 금액)
= max(P[3], P[2]+DP[1], P[1]+DP[2])
카드 4장 사는데 지불해야하는 최대 금액은
DP[4] = max(P[4], P[3]*1+P[1] , P[2]*2, P[2]+P[1]*2 ) = 8원
= max(4장 들어있는 카드팩 하나 사는 금액,\
3장 들어있는 카드팩 하나 사는 금액 + 1장 카드 사는 최대 금액,\
2장 들어있는 카드팩 하나 사는 금액 + 2장 카드 사는 최대 금액,\
1장 들어있는 카드팩 하나 사는 금액 + 3장 카드 사는 최대 금액 )
= max(P[4], P[3]+DP[1], P[2]+DP[2], P[1]+DP[3])
카드 5장 사는데 지불해야하는 최대 금액은
DP[5] = max(P[5], P[4]+P[1] ,P[3]+P[2] \
,P[3]+P[1]*2, P[2]*2+P[1], P[2]+P[1]*3, P[1]*5 ) = 9원
= max(5장 들어있는 카드팩 하나 사는 금액,\
4장 들어있는 카드팩 하나 사는 금액 + 1장 카드 사는 최대 금액,\
3장 들어있는 카드팩 하나 사는 금액 + 2장 카드 사는 최대 금액,\
2장 들어있는 카드팩 하나 사는 금액 + 3장 카드 사는 최대 금액,\
1장 들어있는 카드팩 하나 사는 금액 + 4장 카드 사는 최대 금액)
------------------------------------------------
코드
n = int(input()) # 카드의 개수
p = list(map(int, input().split())) # p
dp = [0 for _ in range(n+1)]
p = [0]+p
dp[1] = p[1]
for i in range(2,n+1):
dp[i] = p[i]
for j in range(1,i):
dp[i] = max(dp[i], p[j] + dp[i-j])
print(dp[n])
✨후기
dp문제인데 갈피를 못잡아서 이분의 글을 참고해서 이해했다. 어렵다 ㅠ
Author And Source
이 문제에 관하여([python/백준] 11052 : 카드 구매하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yje876/python백준DP-11052-카드-구매하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)