11052: 카드 구매하기

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

11052번: 카드 구매하기

설명

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램 작성. 이때, N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것을 불가능. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다. 

 

• 카드는 카드팩의 형태로만 구매 가능.
• 각 카드에는 등급이 있고 8가지 등급으로 나뉘어짐.
• 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... , 카드 N개가 포함 된 카드팩과 같이 총 N가지가 존재.
• 민규는 최대한 많은 돈을 지불해서 카드 N개를 구매하려고 한다. 카드 i개가 포함된 카드팩의 가격은 Pi원이다.

핵심 아이디어

• 다이나믹 프로그래밍
• 작은 문제부터 생각해보자! 카드를 한 개 구매하는 것 부터 시작. 1부터 n까지 각각의 카드 수를 위한 금액의 최댓값을 구해나가는 것.
• dp[i] = 카드 i개 구해하는 최대 가격, p[k] = k개가 들어있는 카드팩 가격

# 3 5 15 16을 예로 들자
# dp[i] = 카드 i개 구매 하는 최대 가격, p[k] = k개가 들어있는 카드팩 가격
dp[1] = 3 # dp[1] == p[1] -> dp[0] + p[1]
dp[2] = 8, max(dp[1] + p[1], p[2]) # 1나 짜리 2개 구매 or 2개짜리 하나 구매
# 하나 * 3 또는 하나 + 두 개 또는 세 개 * 1
dp[3] = 15, max(dp[2]+ p[1], dp[1] + p[2], p[3]) 
# 하나 * 4, 두 개 * 2, 하나 + 세 개, 네 개
dp[4] = 18, max(dp[3] + p[1], dp[2] + p[2], dp[1] + p[3], p[4])

이를 점화 식으로 풀어내면 다음과 같다. dp[i] 에 대해서 j는 1부터 i까지 증가하면서 dp[i] = dp[i-j] + p[j](j값에 따른 max값)

dp[i] = dp[i-k] + p[k] (k값에 따른 max값)

인덱스를 0부터 하면 헷가리는 감이 있어서 dp[0] 은 0으로 채우고 1부터 시작했다.

코드 구현

n = int(input())
p = [0] + list(map(int, input().split()))

dp = [0] * (n+1) # dp = [0] * 1001 가능

# 반복문을 통해 각 카드 개수의 지불하는 최대 금액 구하기
for i in range(1, n+1):
	for k in range(1, i+1):
		dp[i] = max(dp[i], dp[i-k] + p[k])
print(dp[n])

---

반복문을 통해 각 카드 개수의 지불하는 최대 금액을 구해 준다. 각 카드 개수의 지불하는 최대 금액과 이전의 카드를 지불한 최대 금액 + 현재 카드팩 가격을 비교한다.