[Python] 백준 11052번 - 카드 구매하기

문제

11052번: 카드 구매하기

[ 문제 조건 ]

• 카드 개수 < 가격
• i개의 카드, 가격은 Pi
• 즉, 가격을 최대값으로 구해야 한다.

[ 예제 풀이 ]

#1장 샀을때 최대가격 dp[1] =1 
dp[1] = dp[1], dp[0] + list[1] 

#2장 샀을때 최대가격 dp[2] = 5 
dp[2] = dp[2], dp[1] + list[1] #1 + 1 (1장짜리 2개) 
dp[2] = dp[2], dp[0] + list[2] #0 + 5 (2장짜리 1개) 

#3장 샀을때 최대가격 dp[3] = 6 
dp[3] = dp[3], dp[2] + list[1] #5 + 1 (2장짜리 1개 + 1장짜리 1개) 
dp[3] = dp[3], dp[1] + list[2] #1 + 5 (1장짜리 2개 + 2장짜리 1개) 
dp[3] = dp[3], dp[0] + list[3] #0 + 6 (3장짜리 1개) 

#4장 샀을때 최대가격 dp[4] = 10 
dp[4] = dp[4], dp[3] + list[1] #6 + 1 (3장짜리 1개 + 1장짜리 1개) 
dp[4] = dp[4], dp[2] + list[2] #5 + 5 (2장짜리 2개) *정답* 
dp[4] = dp[4], dp[1] + list[3] #1 + 6 (1장짜리 1개 + 3장짜리 1개) 
dp[4] = dp[4], dp[0] + list[4] #7 (4장짜리 1개)

[ 점화식 ]

dp[i] = max (dp[i-j], dp[i-j] + list[j] )

✏️한줄평

다이나믹 프로그래밍 알고리즘의 정석 같은 느낌의 문제다. 점화식을 세우는 건 그래도 헷갈린다. 예제를 풀이하다가도 왜 이게 이 값이였지 헷갈리는게 DP 문제인 듯 하다😅

---

코드

	N = int(input())
	list = [0] + list(map(int, input().split())) #가격
	dp = [0 for _ in range(N+1)] #카드 i개를 구매할 때 최대가격
	# N개인 경우의 수를 구해야함
	for i in range(1, N+1):
	for j in range(1, i+1):
	dp[i] = max(dp[i], dp[i-j] + list[j] )
	print(dp[N])

view raw BOJ11052.py hosted with ❤ by GitHub