[백준 11052번 / C++] 카드 구매하기

DP를 활용한 문제이다. 

 

#접근방법 

 

예를 들어 카드 3개를 사려고 한다. 

DP 배열의 인덱스 번호의 의미는 카드의 개수를 나타내고 카드의 개수만큼 살 수 있는 최댓값을 가지고 있다. 

그렇다면 dp[3] 에는 카드 3개를 살 수 있는 최대 비용이라고 이해하면 된다. 

 

1. dp[2] (두개를 샀을 때 최댓값) + cost[1] (카드 한장 묶음 비용) 

2. dp[1] (한개를 샀을 때 최댓값) + cost[2] (카드 두장 묶음 비용) 

3. dp[0] (0개를 샀을 때 최댓값) + cost[3] (카드 세장 묶음 비용) 

 

즉 이 3가지의 최댓값을 dp[3]에 갱신해주면 된다. 

 

점화식은 아래와 같다. 

" DP[i] =max( DP[i] ,  (DP[i-j] + cost[j])) "

 

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

int main() {
	int n; cin >> n; 
	vector <int> cost(n + 1); 
	for (int i = 1; i <= n; i++) {
		cin >> cost[i]; 
	}
	vector <int> dp(n + 1, 0 ); 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			dp[i] = max(dp[i], dp[i - j] + cost[j]); 
		}
	}
	cout << dp[n]; 
}

 

11052번: 카드 구매하기