[백준][11055] 가장 큰 증가 부분 수열

가장 큰 증가 부분 수열 문제 링크

[풀이]
다이나믹 프로그래밍으로 풀었다. 다이나믹 프로그래밍으로 풀 수 있는 기준은 간단히 말해서는 큰문제를 작은 문제로 나눌 수 있는지이다.

이 문제에 경우 "DP[a] = b" (index a까지의 최대값이 b, index 0부터 시작)로 놓고 시작하였다. DP는 초기화 값으로 index가 가리키는 값으로 놓았다. 왜냐하면 최소한 자기자신의 값이 최대값일 것이기 때문이다.

1) 4 1
2) 4 1 2
3) 4 1 2 3 5

1)로 인해 DP[1]를 구하기 위해서는 전 index와 대소 비교를 해야한다는 것을 알 수 있었고,
2)를 통해 현재 index가 가리키는 값보다 작게 되면 더해주면 된다는 것을 알 수 있었다. 3)을 보면 index4에 입장에서는 index 0이랑 index 3모두 후보가 되어야 한다. 따라서 DP[4] 랑 DP[0]+arr[4] 그리고 DP[3]+arr[4]을 대소비교하여 가장 큰 것이 DP[4]에 들어가면 될 것이다.

[코드]

#include <iostream>
#include <vector>
#define N_MAX 1001

using namespace std;

int N;
int arr[N_MAX];
long long DP[N_MAX];

long long solve(int idx, int prev) {
	long long max_value = -1;
	for (int i = 0; i < N; i++) {
		DP[i] = arr[i];
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i] && DP[i] < DP[j] + arr[i]) {
				DP[i] = DP[j] + arr[i];
			}
		}
		if (max_value < DP[i]) max_value = DP[i];
	}
	return max_value;
}

int main() {
	cin >> N;
	for (int n = 0; n < N; n++) {
		cin >> arr[n];
	}
	long long ans = solve(0,0);
	cout << ans << "\n";
}

[총평]
한번에 못 풀고 답을 보고 이해 한 후 풀게 되었다... 그냥 쉬운 다이나믹 프로그래밍은 아니었던 것 같다.

[참고]
https://yabmoons.tistory.com/87