오늘 푼 문제

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

카드 구매하기

• 풀이 방식

dp를 사용하여 풀었다.
dp[1] = PI[1]
dp[2] = max(dp[1] + dp[1], PI[2])
dp[3] = max(dp[2] + dp[1], PI[3])
dp[4] = max(dp[3] + dp[1], dp[2] + dp[2], PI[4])
....

다음 점화식을 보면 모든 값의 최대값 비교는 해당 카드 N개수와 dp값을 비교하는 방식이다.

또, dp값을 도출해내는 점화식 dp[t]와 dp[i - t]이 나돈다.

따라서, 다음 점화식은 max(dp[i], dp[t] + dp[i - t]) 이다.

나의 풀이

#include <iostream>

using namespace std;

int dp[10001];
int PI[10001];

int main() {

	int N;

	cin >> N;

	for (int i = 1; i <= N; i++) {
		cin >> PI[i];
	}

	dp[1] = PI[1]; 

	for (int i = 2; i <= N; i++) {
		dp[i] = PI[i];
		for (int t = 1; t < i; t++) {
			dp[i] = max(dp[i], dp[t] + dp[i - t]);
		}
	}

	cout << dp[N] << endl;

	return 0;
}