[BOJ] 11052 "카드 구매하기" 문제 풀이 & 소스 코드 with C/C++

#INFO

난이도 : SIVLER1

알고리즘 유형 : 다이나믹 프로그래밍(DP)

∞ 문제 출처 : 11052번: 카드 구매하기 (acmicpc.net)

11052번: 카드 구매하기

---

#SOLVE

돈을 최대한 많이 지불해서 카드 N개를 구매하는 것이 문제의 목표이다. 카드팩이 N개 주어졌을 때, 마지막 카드팩의 개수가 포인트이다. 

마지막 카드팩에 들어있는 카드의 개수가 i개라고 가정할 때, 나머지 카드팩에 들어있는 카드의 개수는 N - i 개 이다.

DP[N] = N개의 카드를 구매하는 최대 가격 이라고 하면, DP[N] = DP[N-i] + i 라는 점화식을 세울 수 있다.

따라서 이를 for 반복문을 이용해 DP로 구현하면 된다.

	//SOLVE
	vector<int> dp(N+1);
	dp[0] = 0;
	for (int i=1; i<=N; i++){
		for(int j=1; j<=i; j++){
			dp[i] = max(dp[i], dp[i-j] + p[j]);
		}
	}

---

#CODE

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

int main()
{	
	int N;
	cin >> N;
	
	vector<int> p(N+1);
	for (int i=1; i<=N; i++){
		cin >> p[i];
	}
	
	//SOLVE
	vector<int> dp(N+1);
	dp[0] = 0;
	for (int i=1; i<=N; i++){
		for(int j=1; j<=i; j++){
			dp[i] = max(dp[i], dp[i-j] + p[j]);
		}
	}	
	
	cout << dp[N] << "\n";
	return 0;
}

---