[백준/C++] 11053 가장 긴 증가하는 부분 수열 (S2)

유형	난이도	완료일	링크	특이사항
DP	실버2	23/02/28	https://www.acmicpc.net/problem/11053	오래 걸림

 

내 풀이

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
	int n;
	cin >> n;
	
	int arr[1000] = {};
	for(int i=0; i<n; i++)
		cin >> arr[i];
	
	int sum[n] = {};
	sum[0]=1;
	
	for(int i = 1; i<n; i++)
	{
		int max = 0;
		for(int j = i-1; j>=0; j--)
		{
			if(arr[j]<arr[i] && sum[j]>max)
			{
				max = sum[j];
			}
			sum[i] = 1 + max;
		}
	}
	
	int ans = 0; 
	
	for(int i= 0; i<n; i++)
	{
		if(sum[i]>ans)
			ans=sum[i];
	}
	
	cout << ans;
}

DP문제의 핵심인 n-1로 n을 구하는 방식에 따라 풀이를 생각했다. 수열을 입력 받는 배열과, 따로 수열의 요소마다 해당 요소까지의 ‘가장 긴 증가하는 부분 수열’의 길이를 저장하는 배열을 만든다(sum[n]).

sum[i]는 arr[i]>arr[j]인 모든 j들을 인덱스로 하는 sum[j]중에서 가장 큰 값에 +1을 하는 것으로 구한다. 즉 이전까지의 가장 길고 자기자신이 이어질 수 있는 부분 수열을 찾아 그 길이에 +1한 값을 취하는 것이다. 이렇게 하면 sum의 모든 요소들은 자신이 수열의 마지막 요소로써 수열에 포함된 경우 가질 최대 길이를 나타낸다. 따라서 sum 중 가장 큰 값이 정답이 되는 것이다.

배열 요소 하나마다 그 요소보다 작은 인덱스의 모든 요소를 탐색하므로 시간복잡도는 O(n^2)이다. DP적으로 해결하는 방식은 이렇다. 하지만 Binary Search를 사용하면 O(nlogn)으로 해결이 가능하다는 것을 알게 되었다.

이 문제와 같이 증가하는 가장 긴 부분 수열을 LIS(Longest Increasing Subsequence)라고 한다. Binary Search를 활용해 최장 수열의 길이를 구해내는 방법이 존재했다.

 

다른 풀이(숫자만 다른 LIS문제)

https://paris-in-the-rain.tistory.com/97

LIS를 이분탐색으로 구하는 코드다. 정답을 저장할 배열(실제 LIS는 여러개일 수 있으므로 길이만 똑같다)에 주어진 배열 순서대로 입력 받으며, 맨 뒤 원소보다 크면 그대로 저장하고 작을 경우 주어진 값보다 작지 않은 값의 위치에(lower_bound로 찾음) 값을 교체해 넣는다(무조건 오름차순으로 저장하므로 이분탐색이 계속 가능하다).

마지막 요소까지 이 과정을 거치면 정답 저장 배열의 요소 수가 곧 정답이 된다.

즉 어떤 수를 현재 최장 길이인 배열에 이어 붙일 수 없다면(마지막 요소보다 더 크지 않다면) 최대한 더 작은 수를 배열에 포함하겠다는 알고리즘이다. 그렇게 하는 경우가 더 많은 요소를 포함할 가능성이 높아지기 때문이다.

이분탐색을 활용한 lower_bound 함수가 있는지 처음 알았다. 지금 실버2 문제는 이분탐색 활용까지 바란 문제는 아니었는데 앞으로 이분탐색을 활용할 문제가 많아질 것 같다. 마음의 준비를 하고 배운 알고리즘이라면 뭐든 사용해볼 생각을 해야겠다.