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

문제

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

풀이

[DP, LIS 알고리즘]

숫자를 차례대로 확인한다.

이번에 확인하는 숫자 n의 이전 값들 중에

n보다 크고, dp값도 큰 m이 있다고 하면

m의 dp값+1 로 n의 dp값을 갱신한다.

m과 연결된 부분 수열이 되는 것이다.

예시

10 30 10 20 20 10 에서 숫자를 차례대로 보자

 

이번 차례가 4번째에 있는 20이라고 하자

0~3번째 숫자를 보며 20보다 큰 것이 있나 확인할 것이다

앗 30이 더 크다!

30즉 dp[1]의 값은 1이다.

20즉 dp[3]의 값은 1이다.

dp[1]+1이 dp[3]보다 더 큰값이므로 dp[3]=2로 갱신된다.

 

이번 차례가 5번째에 있는 10이라고 하자

0~4번째 숫자를 보며 10보다 큰 것이 있나 확인한다.

30,20,20이 더 크다

여기서 20 즉 dp[3]의 값은 2으로 가장 크다

dp[3]+1이 dp[5]보다 크므로 dp[5]=3으로 갱신된다.

코드

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

int main()
{
	int N; cin >> N;
	vector<int>number(N);
	vector<int>dp(N,1);
	for (int i = 0; i < N; i++) 
	{ 
		cin >> number[i]; 
		for (int j = 0; j < i; j++)
		{
			if (number[j] > number[i]) { dp[i] = max(dp[i], dp[j] + 1); }
		}
	}

	cout << *max_element(dp.begin(), dp.end());
}