[백준] 11055번 가장 큰 증가하는 부분 수열 C++ 코드

코드

#include <iostream>
#include <cstring>

using namespace std;

int n, a[1003], dp[1003][1003];

int go(int idx, int num) {
	if (idx == n) return 0; // 끝까지 가면 함수 종료
	int &ret = dp[idx][num];
	if (ret != -1) return ret; // 메모이제이션
	ret = go(idx + 1, num); // 부분수열에 포함 X case
	if (num < a[idx]) { // 현재 값이 더 큰 경우
    	// 부분수열에 포함한 케이스와 포함하지 않는 케이스 비교
		ret = max(ret, go(idx + 1, a[idx]) + a[idx]);
	}
	return ret;
}

int main() {
	cin >> n;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < n; i++) cin >> a[i];
	
	cout << go(0, 0) << '\n';
	return 0;
}

풀이

가장 큰 증가하는 부분 수열을 찾는 문제이다. ret 변수에 포함하지 않는 값을 저장해두고 만약 a[idx]가 이전 값보다 더 큰 값이면 포함하지 않은 값과 포함한 값을 비교해 더 큰 값을 저장한다.