11722) 가장 긴 감소하는 부분 수열 c++

문제 ) www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

 

풀이 ) 11053 문제를 먼저 풀었어서 조금 쉬웠다.

문제에서 dp 배열은 가장 긴 증가하는 부분 수열의 길이를 저장하는 배열로 사용했다.

1. 수열 A의 크기가 최소 1이라고 했으므로 dp[i] = 1 로 세팅하고 시작

2. A배열의 맨처음 수부터 계속해서 비교하기 위해서 j의 범위를 i까지 만으로 지정

3. 현재 비교할 수열의 값이 바로 직전의 값보다 작을 경우
   예를들어 A[i] = 10, < A[j] = 30인 경우

4. 감소하는 부분 수열의 길이를 하나 증가해야하므로 dp[i]값을 바꿔준다.

5. sum 변수에는 dp배열 즉 수열 길이의 가장 큰 값만 넣어서 반환한다.

 

코드 ) 

#include <iostream>
#include <algorithm>
using namespace std;

int N, sum;
int A[1001];
int dp[1001];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N;
	for(int i=0; i<N; i++)
		cin >> A[i];
	
	for(int i=0; i<N; i++) {
		dp[i] = 1;						// 1
		
		for(int j=0; j<i; j++) {				// 2
			if( A[i] < A[j] ) {				// 3
				dp[i] = max(dp[i], dp[j]+1);		// 4
			}
		}
		sum = max(sum, dp[i]);					// 5
	}
	cout << sum;
}