[백준 C++] 11722번: 가장 긴 감소하는 부분 수열

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

 

가장 긴 감소하는 부분 수열

 

가장 긴 증가하는 부분 수열을 반대로 하면 되지 않을까 한다. 

 

윈리는 dp[1001]과 수열을 담을 a[1001]을 선언한 뒤 dp[i]는 i번째 원소로 끝나는 부분 수열 중 가장 긴 감소하는 부분수열의 길이를 저장한다. 

 

그러기 위해서는 일단 dp[i]는 1로 모두 초기화해주고 (항상 자기 자신을 포함하는 수열은 길이가 1이기 때문)

 

i-1부터 0까지 반복하는 for문을 통해 a[j]값이 a[i]값보다 큰 경우에 dp[i]는 기존값과 dp[j] + 1값중 더 큰값을 저장하게 된다.

이렇게 a[0]까지 찾은 뒤 dp[i]가 확정되었으면 max값과 비교하여 가장 큰값(가장 긴 수열)을 저장해준뒤 마지막에 리턴해준다.

 

#include <iostream>
#include <algorithm>
#define MAX 1001
using namespace std;
int dp[MAX] = { 0, };
int a[MAX] = { 0, };
int main(int argc, char* argv[])
{
	int n, max1 = 0;
	cin >> n;
 
	for (int i = 0;i < n;i++) {
		cin >> a[i];
	}
 
 
	for (int i = 0; i < n;i++) {
		dp[i] = 1;
		for (int j = i - 1;j >= 0;j--) {
			if (a[i] < a[j]) {
				dp[i] = max(dp[i],(dp[j] + 1));
			}
		}
		max1 = max(max1, dp[i]);
	}
 
	cout << max1;
 
	return 0;
}

 

이전에 풀었던 가장 큰 증가 부분수열에서 조금만 바꾸어서 코드를 짜면 되서 쉽게 풀었던 문제이다.

 

원리를 깨닫고 나면 쉬운 문제.