백준 Silver 1 카드 구매하기

카드 구매하기 (백준 Silver 1)

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

민규가 모으는 카드의 개수는 n개이며
n개의 카드가 들어있는 n개의 카드팩의 가격이 주어진다

민규는 이상한? 미신을 믿고 있기에
가능하면 n개의 카드를 구매하기 위하여
가장 많은 돈을 사용하려 한다

민규가 n개의 카드를 구매할 때의
가장 큰 비용을 구하는 문제

풀이 방식

일단 dp 문제이기에 점화식을 세우는 것을 목표로 하였다
(n개 구매를 목표로 할때, 다른 n-1개 등의 값을 재활용이 가능해 보였으므로)

점화식 정의
dp[n] : n개의 카드를 모을때 사용하는 가장 큰 가격

초기 조건
dp[0] = 0 : 0개의 카드는 돈이 필요 없으므로
dp[1] = cards[1] : 1개의 카드만 필요하다면 첫번째 카드팩만 구매해야 함

그렇기에
dp[2] = max(cards[2],dp[1] + dp[1]) 이라고 생각하였다

조금 더 생각해보니
‘이전 값’을 더하는 것은 맞지만
n개의 ‘카드’를 모으려면 사실
1~n까지 돌았을 때

dp[3] = cards[3] , dp[2] + dp[1]
dp[4] = cards[4] , dp[1] + dp[3], dp[2] + dp[2]
…

인것으로 보아

dp[n] = cards[n] , dp[1] + dp[n-1], dp[2] + dp[n-2]…
가 되는 것을 판별할 수 있었다

따라서 dp[n] 의 초기값을 cards[n]으로 놓은 후
1~n까지 돌면서 dp[j] + dp[i-j]를 돌리면 되겠다 싶었다
(실제로는 n/2 까지만 돌면 된다)

완성된 점화식
dp[n] = max(cards[n], for(1~n/2) max(dp[n],dp[j] + dp[i-j]))

제출 코드

#include<iostream>
#include<vector>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> cards(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> cards[i];

	vector<int> dp(n + 1);
	dp[0] = 0;
	dp[1] = cards[1];

	for (int i = 2; i <= n; i++)
	{
		dp[i] = cards[i];

		for (int j = 1; j <= i / 2; j++)
		{
			dp[i] = max(dp[i], dp[i - j] + dp[j]);
		}
	}

	cout << dp[n];

	return 0;
}

결과

이번 문제는 점화식을 잘 세울 수 있었다