[C/C++ 백준 11052번] 카드구매하기 (Silver 1)

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

11052번: 카드 구매하기

i번째 카드까지 구매하는데 가장 큰 금액을 dp[i]라 하자. dp[i+1]을 정할때 Pi[i+1] (해당 단일 카드팩 구매시 금액) ,dp[1]+dp[i], dp[2]+dp[i-1], ....를 모두 비교해 가장 큰 값으로 정하면, 모든 경우를 따질 수 있다. 사이트에 나와 있는 예제들을 이용해 알고리즘을 따져보면 검증해 볼 수 있다. 비교적 간단한 문제였던것 같다.

---

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
	int N, Pi[10001]={0,}, dp[10001]={0, };
	scanf("%d",&N); 
	for(int i=1; i<=N; i++){
		scanf(" %d", &Pi[i]);
		int maxi=Pi[i];
		for(int j=1; j<i/2+1; j++)
			maxi=max(maxi, dp[j] + dp[i-j]);
		dp[i]=maxi;
	}
	printf("%d",dp[N]);
}

---