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

문제 링크 => 11722번: 가장 긴 감소하는 부분 수열 (acmicpc.net)

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

---

다이나믹 프로그래밍 문제이다.

 

dp 값을 어떻게 변경할 것인지에 대해서 약간 까다로운 문제인것 같다.

 

배열의 어떠한 값을 기준으로 왼쪽에 있는 값들과 비교해가면서 다음과 같은 조건을 만족하는 경우를 찾는다.

• 왼쪽의 값이 기준으로 둔 값보다 큰 경우를 찾는다. ( arr[j] > arr[i] )
• 그때의 dp값에 1을 더한 값으로 즉, 왼쪽의 값이 감소하는 길이에 1을 더한 값보다 작은 경우를 찾는다. ( dp[j] + 1 > dp[i] )

위 조건을 동시에 만족하는 경우 dp[i] 값을 dp[j] + 1 로 변경한다. 

 

이런 유형의 문제가 어려워서 자주 보도록 해야겠다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

int arr[1000];
int dp[1000];

void solve(int n) {
	int res = 0;
	for (int i = 0; i < n; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (arr[j] > arr[i] && dp[j] + 1 > dp[i])
				dp[i] = dp[j] + 1;
		}
		res=max(res,dp[i]);
	}
	cout << res;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	solve(n);
	
	return 0;
}