[백준][C++] 11053번: 가장 긴 증가하는 부분 수열

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

11053번: 가장 긴 증가하는 부분 수열

 

수열이 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다.

 

DP의 느낌이 강하게 들어서 DP로 풀어보았다.

 

먼저 DP[i]는 수열의 i번째에 가장 긴 증가하는 수열의 길이로 정의하고 점화식 찾기에 들어갔다.i번째 전까지 i번째 원소보다 작은 원소들 중 가장 긴 부분 수열의 길이 값을 찾아야 하므로 이중 반복문을 사용하여 비교할 원소가 i번째 원소보다 작다면 DP[i]값과 DP[비교 원소의 위치]+1 중 더 큰 값을 DP[i]에 저장하면 되겠다 생각했다.

 

#include<iostream>

using namespace std;

int A[1001];
int DP[1001];

int Max(int a, int b) {
	if(a>=b) return a;
	else return b;
}

int main(void) {
	int N;
	cin >> N;
	for(int i=0; i<N; i++) {
		cin >> A[i];
	}
	
	int answer = 1;
	DP[0] = 1;
	for(int i=1; i<N; i++) {
		DP[i] = 1;
		for(int j=i-1; j>=0; j--) {
			if(A[j] < A[i]) {
				DP[i] = Max(DP[i], DP[j]+1);
			}
		}
		answer = Max(answer, DP[i]);
	}
	
	cout << answer;
}

 

 

DP[N-1] 값이 최장 길이가 아니라 수열의 각 원소마다 증가하는 부분 수열의 길이를 비교해가며 최장 길이를 찾아야 한다.