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

문제 링크

문제#

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 $A = \{10, 20, 10, 30, 20, 50\}$인 경우에 가장 긴 증가하는 부분 수열의 길이는 4이다.

입력#

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 $A$를 이루고 있는 $A_i$가 주어진다. $(1 \le A_i \le 1{,}000)$

출력#

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

풀이#

각 위치를 마지막 원소로 하는 증가 부분 수열의 최대 길이를 구해 두면 된다. 그래서 현재 수보다 앞에 있으면서 더 작은 수들을 살펴보고, 그중 가장 긴 길이에 1을 더하는 DP가 기본이 된다.

코드에서는 i번째 수를 기준으로 이전 위치들을 확인하면서 dp[i]를 갱신한다. 자기보다 작은 값 뒤에만 붙을 수 있다는 조건이 전이의 핵심이다.

결국 부분 수열 자체를 저장할 필요는 없고, 각 위치에서 끝나는 최장 길이만 남기면 충분하다. 증가 조건을 어떻게 전이로 옮기느냐가 핵심이다.

코드#

#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[1001];
int LIS[1001];
 
void solve() {
 
	int n, ans = 1;
	cin >> n;
 
	fill_n(LIS, n, 1);
 
	for (int i = 0; i < n; i++)
		cin >> arr[i];
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if(arr[i] > arr[j]) 
				LIS[i] = max(LIS[i], LIS[j] + 1);
		}
		
		ans = max(ans, LIS[i]);
	}
	
	cout << ans << '\n';
}	
 
int main() {
    
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	solve();
 
    return 0;
}

복잡도#

• 시간 복잡도: 각 원소마다 앞의 원소들을 확인하므로 $O(N^2)$이다.
• 공간 복잡도: LIS 길이 DP 배열을 저장하므로 $O(N)$이다.

마무리#

각 위치에서 끝나는 LIS 길이만 잡아도 기본 증가 부분수열 문제는 충분히 풀린다.