[BOJ 11053] 가장 긴 증가하는 부분 수열

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

수열이 주어졌을 때 주어진 수열에서 가장 긴 수열의 길이를 구하는 문제입니다.

여기서 수열의 길이라는 것은,

어떠한 숫자 x로부터 x보다 큰 숫자들을 쭉 이어나갔을 때의 길이를 말합니다.

Longest Increasing Subsequence라고 부릅니다.

 

6

10 20 10 30 20 50

 

첫 번째 원소 10을 선택하여 LIS를 만들 수 있는 경우 : 10 → 20 → 30 → 50으로 길이 4

두 번째 원소 20을 선택하여 LIS를 만들 수 있는 경우 : 20 → 30 → 50으로 길이 3

세 번째 원소 10을 선택하여 LIS를 만들 수 있는 경우 : 10 → 30 → 50 OR 10 → 20 → 50으로 길이 3

네 번째 원소 30을 선택하여 LIS를 만들 수 있는 경우 : 30 → 50으로 길이 2

다섯 번째 원소 20을 선택하여 LIS를 만들 수 있는 경우 : 20 → 50으로 길이 2

​

만약 모든 숫자가 60 50 40 30 20 10 으로 내림차순으로 되있다면 항상 답은 1입니다. [자신만 선택하는 경우]

같은 논리로 예시에서 마지막 숫자만 선택할 경우 마지막 원소 50은 항상 길이가 1입니다.

​'x라는 어떤 지점까지 왔을때의 최댓값을 이용하여 x보다 더 큰 y지점의 값을 구할 때 이용할 수 있는가?'

이용할 수 있다면, subproblem을 이용하여 원하는 문제를 풀 수 있기 때문에 동적계획법으로 풀이합니다.

10	20	10	30	20	50
1	2	1	3	2	4

두 번째 20까지 갈 때는 10을 거쳐오는게 가장 최적의 상태이기 때문에 20까지 도착했을 때의 최댓값 1 

세 번째 10은 그 이전에 자기보다 어떠한 '작은값'이 없음. 세번 째 10의 상태에서는 최댓값 1

네 번째 30은 그 이전에 자기보다 작은값들만 존재하는데, 이 중에서 '가장 큰 최댓값'을 가져오는게 이득,

20에 머물렀을 때의 값 2에다가 +1을 해주어 30의 경우에는 3

다섯 번째 20은 그 이전에 자기보다 작은 값이 10이 두 가지(첫 번째, 세번째) 존재하는데 이 중 가장 큰 값을 가져오는게 이득. 두 값이 동일하기 때문에 1 + 1을 해주어 20의 경우에는 2

여섯 번째 50은 그 이전의 값들이 모두 자기 자신보다 작음. 그러므로 가장 긴 길이를 가지고 있는 30을 선택하여

3 + 1을 해주어 4

​

위의 논리를 바탕으로 어떤 지점 x에서의 최댓값을 구하려면,

x지점 이전의 지점에서 x지점의 값보다 작은 값이 있다면,

그 값들을 가지고 이용을 하되 그 중에서 '최댓값'을 이용해 갱신해줍니다.

작은 값이 있는데 안거치고 왔다는 것은, 증가수열의 논리에 위배됩니다.

 

이 방식은 어떤 지점 x를 기준으로 이전의 지점을 전부 다 탐색하여 최댓값을 갱신하기 때문에,

O(n^2)의 시간복잡도를 가집니다.

​

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

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

	int Max = -1;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (v[i] > v[j])
			{
				arr[i] = max(arr[j], arr[i]);
			}
		}
		arr[i] = arr[i] + 1;
		Max = max(Max, arr[i]);
	}

	cout << Max;
}