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

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 1 ~ n 종류의 카드팩까지 있을 때 1 ~ n 개의 카드를 사는 최대 금액을 2차원 dp 배열에 차례대로 갱신하는 Bottom-Up 방식으로 풀었다.

• 이 문제는 평범한 배낭 문제와 유사하나, 배낭 문제는 현재 순서 물건이 하나밖에 존재하지 않는 반면, 해당 문제는 같은 물건(== 카드팩)을 여러 개 사용 가능하다.
• 따라서 현재 순서 물건을 넣는 경우에 현재 물건을 포함하는 경우의 dp값을 참조한다.
  (배낭 문제는 직전 물건까지만 있을 때의 dp를 참조)

1) n에 구매하고자 하는 카드의 개수를 입력받아 저장한다.

2) 2차원 배열 dp를 선언하고, 각 dp를 차례대로 갱신한다.

• dp[i][j] : i 번째 카드팩까지 있을 때, j개의 카드를 사는 최대 금액
• 문제 조건에 의해 n개보다 많은 개수의 카드를 살 수 없다. 따라서 현재 순서의 카드팩으로 j개의 카드를 사는 경우는 두 가지로 나뉜다.
  • 현재 순서 카드팩에 사고자 하는 카드 개수보다 많은 카드가 들어있을 때 (i > j)
    : 이 때는 현재 순서(i) 카드팩으로 j개의 카드를 살 수 없으므로 직전 순서(i-1) 카드팩까지 있을 때 j개의 카드를 사는 최대 금액과 같다.
  • 위 경우가 아닐 때는 아래 두 경우 중 큰 값을 dp[i][j]로 갱신한다.
    • 현재 순서 카드팩을 무조건 한 개 이상 넣는 경우
      : 현재 순서 카드팩까지 있을 때 (j-현재 순서 카드팩 개수)개 카드 사는 최대 금액 + 현재 순서 카드팩의 금액
    • 현재 순서 카드팩을 사지 않는 경우
      : 직전 순서 카드팩까지 있을 때 j개의 카드 사는 최대 금액
• 위 과정을 점화식으로 나타내면
  • 각 i와 j에 대해 (i : 현재 카드 순서 (1 ~ n) / j : 사고자 하는 카드 개수 (1 ~ n))
  • if(i > j) dp[i][j] = dp[i - 1][j]
  • else dp[i][j] = max(dp[i][j - i] + costs[i], dp[i - 1][j])

3) dp[n][n]에 카드 종류가 n가지 있을 때, n개의 카드를 사는 최대 금액이 저장되므로 이를 출력한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
vector<int> costs;
int dp[1001][1001];		// dp[i][j] : i 번째 카드팩까지 있을 때 j개의 카드를 사는 최대 금액

int solution() 
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i > j)		
				dp[i][j] = dp[i - 1][j];
			else			
				dp[i][j] = max(dp[i][j - i] + costs[i], dp[i - 1][j]);			     
		}
	}
	return dp[n][n];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n;
	costs.push_back(0);
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		costs.push_back(num);
	}
	cout << solution();
}