[동적계획법, 난이도 중] 백준 11053번 가장 긴 증가하는 부분 수열

제한 시간은 1초며, N의 범위가 (1 ≤ N ≤ 1,000) 으로 좁은 편이기 때문에 O(N^2) 까지 쓸 수 있다.

그래도 이 문제는 1차원 배열의 DP로 풀 수 있다.

 

첫 INPUT에 대한 DP의 첫 인덱스 값을 1로 두며 시작한다.

그리고 이 조건에 따라 뒤 INPUT값들에 대해 DP를 수행해주면 된다.

• 현재 INPUT값보다 작은 모든 이전 INPUT값들의 각 DP값들중 최댓값에 1을 더한 값을 현재 DP값으로 지정한다.

만약 현재 INPUT값이 30이라면 이전 INPUT값들은 각각 10, 20, 10이고, 이들의 각 DP값은 1,2,1이다.

1,2,1의 최댓값은 2이기 때문에 이에 1을 더한 3을 현재 DP값으로 지정하는 것이다.

 

현재 INPUT값이 지금까지 나온 INPUT값들중 최솟값일 경우가 있는데, 이 때는 DP값을 1로 지정해준다.

 

최종적으로 완성한 DP배열의 최댓값이 가장 긴 증가하는 부분 수열의 크기가 된다.

 

 

#include <iostream>
using namespace std;
int save[1001];
int input[1001];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i < n + 1; i++) {
		cin >> input[i];
	}
	save[1] = 1;
	for (int i = 2; i < n + 1; i++) {
		int max = 0;
		for (int j = 1; j < i; j++) {
			if ((input[j] < input[i])&&(save[j]>max)) {
				max = save[j];
			}
		}
		if (max == 0) save[i] = 1;
		else save[i] = max + 1;
	}
	int base = save[1];
	if (n > 1) {
		for (int i = 2; i < n + 1; i++) {
			if (save[i] > base) base = save[i];
		}
	}
	cout << base;
}