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

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/11053

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

 

아주 전형적인 LIS 문제였다.

 

LIS는 Longest Increasing Subsequence의 준말로, 

주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제이다.

부분 수열은 연속적일 필요가 없다는 것을 명심하자.

 

만약, 부분 문자열(substring)이었다면 문제가 훨씬 쉬워졌을 거다.

for문 한번 훑으면서 O(n)에 답을 찾을 수 있기 때문이다.

 

하지만 부분 수열의 경우에는 dp의 성질을 활용하게 된다.

따라서 각 인덱스에 대해 LIS 값을 저장해 둘 n크기만큼의 일차원 배열을 할당한다.

이제 이중 for문을 통해 O(n^2)의 시간 복잡도로 배열 값을 채워 나갈 것이다.

 

먼저 바깥 for문에서 인덱스 0부터 차례로 타겟이 되는 인덱스를 설정한다.

그 후 안쪽 for문에서 인덱스 0부터 타겟 인덱스 - 1 까지의 배열 값을 타겟 인덱스의 배열 값과 비교한다.

 

만약 타겟 인덱스의 배열 값이 더 크다면 문제가 요구하는 오름차순으로 정렬된 부분 수열에 해당한다.

또한 디피 배열 값은 각 인덱스의 LIS 길이, 즉 가장 긴 부분 수열의 값을 저장해야 하므로

비교 인덱스 배열에 저장되어 있는 LIS에 현재 타겟 인덱스의 배열 값을 추가한 길이가 최대가 되도록 조건을 걸어줘야 한다.

 

3 4 1 5를 예시로 들어보자.

idx	0	1	2	3
arr	3	4	1	5
dp

 

dp[0] 은 타겟 인덱스가 0이고 비교할 이전의 인덱스가 없으므로 LIS를 3으로 갖는 길이 1의 값을 갖는다.

 

idx	0	1	2	3
arr	3	4	1	5
dp	1

 

dp[1]은 타겟 인덱스가 1이 되고 비교할 이전의 인덱스는 0 하나다.

 

비교 시작 전 dp[1]은 부분 수열로 arr[1]만을 갖는 경우, 즉 1로 초기화된다.

arr[0] < arr[1]이 되고, dp[0] + 1 < dp[1]을 만족하면 dp[0]이 의미하는 부분 수열에 arr[1]을 원소로 추가하여 부분 수열을 확장할 수 있다.

arr[0] = 3 < arr[1] = 4이고, 인덱스 1만을 부분 수열로 가질 때 dp[1] = 1 < dp[0] + 1 = 2 이므로 dp[1] = 2로 갱신된다.

 

idx	0	1	2	3
arr	3	4	1	5
dp	1	2

 

이제 dp[2]를 구해보자.

 

타겟 인덱스는 2, 비교 인덱스는 0과 1이 있다.

arr[0] = 3 > arr[2] = 1 이므로 증가하는 부분 수열을 이룰 수 없다.

마찬가지로 arr[1] = 4 > arr[2] = 1 이므로 증가하는 부분 수열을 이룰 수 없다.

따라서 dp[2]의 경우 자기 배열 값 1만을 부분 수열로 가지는 경우인 1이 된다.

 

idx	0	1	2	3
arr	3	4	1	5
dp	1	2	1

 

이제 대망의 마지막 인덱스 3에 대한 dp값을 찾아보자.

비교 인덱스는 0, 1, 2 세 개다.

비교 시작 전 dp[3]은 arr[3]만을 부분 수열로 갖는 경우인 1로 초기화되어 있음을 명심하자.

 

arr[0] < arr[3] 이고, dp[0] + 1 > dp[3] 을 만족하므로

dp[3] = 2 로 갱신된다.

즉, 부분 수열로 3 5 를 갖는 경우를 나타낸다.

 

arr[1] < arr[3] 이고, dp[1] + 1  > dp[3]이다.

즉, dp[1]에 저장된 값 2의 의미인 부분 수열 3 4에 arr[3]의 값인 5가 추가되는 경우가 지금까지의 LIS라는 뜻이다.

dp[3] = 3으로 갱신된다. 이는 부분 수열로 3 4 5를 갖는 경우를 나타낸다.

 

반면 arr[2] > arr[3] 이므로 오름차순의 수열을 나타낼 수 없다.

 

즉, 최종 dp 배열은 다음과 같다.

 

idx	0	1	2	3
arr	3	4	1	5
dp	1	2	1	3

 

이를 구현한 코드는 아래와 같다.

 

/*
20200511
baekjoon 11053번 - 가장 긴 증가하는 부분 수열
solved
*/
#include <iostream>
using namespace std;

int arr[1001], dp[1001];
int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> arr[i];
	}

	for (int i = 0; i < n; ++i) {
		dp[i] = 1; //초기값
		for (int j = 0; j < i; ++j) {
			if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
				dp[i] = dp[j] + 1;
			}
		}
	}

	int ans = dp[0];
	for (int i = 1; i < n; ++i) {
		if (ans < dp[i]) {
			ans = dp[i];
		}
	}

	cout << ans;
}