백준 11052

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

11052번: 카드 구매하기

이 문제의 경우 여러방면으로 풀려고 시도 했으나 결국 또 점화식을 계속 이상하게 세워서 빨리 풀지 못했다

이 문제는 점화식만 처음에 방향을 잘잡고 풀었으면 빨리 풀렸을 거 같은 문제였다 일단 이문제는

카드를 1장만 산다고 생각해서 카드 개수를 늘려가면서 점화식을 세우는게 효율적이 었던거 같다.

이 문제의 dp배열은 해당 인덱스 장만큼의 카드를 살때의 최댓값을 나타낸다.

일단 dp배열을 초기화 할때 각배열에 그 장만큼의 카드를 살 때의 가격을 넣어준다

일단 카드 1장을 살 때는 경우의 수가 카드 1장짜리를 사는 경우의 수밖에 없으니  팩의 최댓값을 나타내는 dp[1]의 값이 밑에 처럼된다

dp[1]= 1장 짜리 카드팩의 가격

이런식으로 넣는다

dp[2]= 1장을 샀을 때의 최댓값 +1장을 샀을 때의 최댓값 와 2팩짜리를 샀을 때 중 큰 값을 골라준다

dp[3]= 2장을 샀을때의 최댓값 + 1장 짜리 샀을때의 최댓값과  3팩짜리를 샀을 때의 최댓값을 비교해서 큰값을 골라준다

dp[4] 부터는 경우의  수가 많아진다 

dp[4]= 1장을 삿을때의 최댓값사고 3장을 샀을 떄의 최댓값, 2장을 샀을 때의 최댓값 + 2장을 샀을때의 최댓값 4팩짜리를 샀을 때의 값중 최댓값을 골라서 넣어준다 이것을 간단히 식으로 나타내면

dp[1]=dp[1];

dp[2]=max(dp[1]+dp[1],dp[2])

dp[3]=max(dp[1]+dp[2],dp[2]+dp[1],dp[3])

dp[4]=max(dp[1]+dp[3],dp[2]+dp[2],dp[3]+dp[1],dp[4]) 

이런식으로 규칙성이 발생해서 점화식을 만들수 있다

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001];
int main() {
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> dp[i];
	}
	for (int i = 2; i <= N/2; i++) {
		for (int j = 1; j < i; j++) {
			dp[i] = max(dp[i], dp[j] + dp[i - j]);
		}
	}
	cout << dp[N];
}