[BOJ] 11052번 카드 구매하기(C++)

풀이 소요시간 : 40분

아이디어가 떠오를듯 하면서도 안떠올랐다.

2 는 1+1 로 표현이 가능하며
3 은 1+2 로 표현이 가능하고, 1+1+1 로도 표현이 가능하다.

하지만 DP 풀이법에서는 위의 상황처럼 생각하면 안된다.
3 은 1+2 로 표현이 가능하다. 왜냐하면, 2는 이미 1+1 와 0+2 가 내포되어있기 때문이다.

이 점을 생각하면 Map[1001] 배열을 선언하여 초기값을 하고 차례대로 값을 구해주면 된다.

전체 코드

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

int N;		 
int P[1001]; 
int Map[1001];


int main() {

	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> P[i];
		Map[i] = P[i];
		//초기값
	}

	Map[0] = 0;
	Map[1] = P[1];

	for (int i = 2; i <= N; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			//Map[3] = max(Map[2] + P[1], Map[3])
			//Map[3] = max(Map[1] + P[2], Map[3])
			//Map[3] = max(Map[0] + P[3], Map[3])
			Map[i] = max(Map[i - j] + P[j], Map[i]);
		}
	}

	cout << Map[N] << endl;
}