[BOJ] 백준 11052 카드 구매하기 c++ (DP)

문제 출처 : https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

풀이

DP로 해결하는 문제이다.

---

P1~PN은 card 배열에 넣어주고, dp[i]를 카드 i개를 갖기 위해 지불한 최댓값 이라고 하였다.

 

모든 경우의 수를 고려해야 할 것 같아서, 각 dp(1부터 N)마다 1부터 i장 이하의 카드팩을 구매하는 경우를 고려하였다.

ex) 1장 카드팩을 구매할 경우 dp[N] = dp[N - 1] + card[1] 이다.

2장 카드팩을 구매할 경우 dp[N] = dp[N - 2] + card[2] 이다.

...

i장 카드팩을 구매하면? dp[N] = dp[N - i] + card[i] 이다.

 

이를 통해 점화식을 도출해내면 아래와 같다.

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

---

 

코드

dp[N]을 구하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int N; cin >> N;

	int card[1000 + 1] = {0, };
	int dp[1000 + 1] = {0, }; // dp[i] 는 i개 갖기 위해 지불한 최댓값

	for(int i = 1; i <= N; i++)
		cin >> card[i];

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

	cout << dp[N];

	return 0;
}