11052번: 카드 구매하기

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

11052번: 카드 구매하기

1. 문제 분석

맨 처음엔 가격/카드 개수,카드 개수, 가격으로 tuple을 만들어서 가성비가 안 좋은 순으로 그리디로 하면 풀 수 있을 줄 알았는데 풀 수 없었다.

DP로 푸는 문제 였다.

2. 코드 작성

#include <iostream>
#include <algorithm>

using namespace std;
int price[10001];
int dp[10001];
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int N;
	cin >> N;
	for (int i = 1;i <= N;i++)
	{
		cin >> price[i];
	}

	for (int i = 1;i <= N;i++)
	{
		for (int j = 1;j <= i;j++)
		{
			dp[i] = max(dp[i], dp[i - j] + price[j]);
		}
	}
	cout << dp[N];
	return 0;
}

3. 키워드

#DP

4. 코드 분석

2중 for문이 돌아가는 과정을 보면 된다.

dp[1] = max(dp[1], dp[0] + price[1])

dp[2] = max(dp[2], dp[1] + price[1])

dp[2] = max(dp[2], dp[0] + price[2])

dp[3] = max(dp[3], dp[2] + price[1])

dp[3] = max(dp[3], dp[1] + price[2])

dp[3] = max(dp[3], dp[0] + price[3])

이걸 왜 dp로 구현할 생각을 했을까..?? 일단 sum[N]을 구하려면 sum[N-i]+price[i] (i는 1~N) 중에서 최댓값을 구해야 한다. 그 때마다 sum[N]과 sum[N-i]을 불러와야 하니까 dp 쓸만하다!

sum[N]= sum[N-i]+price[i]을 생각하는 것도 중요했던 것 같다.