[C/C++] 백준 #1365 꼬인 전깃줄(가장 긴 증가하는 부분수열)

백준 알고리즘 사이트에서 많이 나오는 문제 중 하나가 가장 긴 증가하는 부분수열(LIS; Longest Incremental Subsequence)입니다. 

 

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

1365번: 꼬인 전깃줄

 

수열에 있는 수들 중 일부(연속되지 않아도 상관이 없습니다.)를 선택해서 그 순서가 증가하는 수열이면 증가하는 부분 수열입니다.  여기서 문제는 그 증가하는 부분 수열의 길이가 가장 긴 경우가 얼마인지입니다.

 

Tangled Electric Lines

 

가장 일반적인 해법은 동적 프로그래밍을 이용하는 것입니다.  길이가 n인 수열인 \(a_1, a_2, ..., a_i, ..., a_n\)이 주어졌다면, \(a_i\)까지 수열중 가장 긴 증가하는 수열은 그 후에 나오는 \(a_i\)보다 큰 수에 대해서 미리 계산한 결과가 됩니다.  \(a_i\)에서 최장 증가하는 부분 수열의 갯수를 찾아보기 위해서는 왼쪽부터 수열을 찾아보면서, \(a_i\)보다 작은 경우에 dp[*]값의 가장 큰 값을 찾으면 됩니다.  수식으로 표현하면 다음과 같습니다.

 

\[ dp_i = \max_{k \lt i, a_k \lt a_i}(dp_{k}) + 1 \]

 

하지만 이렇게 하면, 알고리즘 효율이 \(O(n^2)\)이 되어서 n이 커지면 시간초과로 문제 풀이에 실패할 수 있습니다.

 

이 문제에서도 N의 최대값이 100,000으로 \(O(N^2)\) 알고리즘으로는 실패할 것입니다.

 

그래서 증가하는 순으로 정렬된 배열을 유지하면서 \(O(N Log N)\) 효율의 알고리즘이 있습니다.

 

배열에 첫번째 숫자를 넣고, 그 다음부터는 배열의 마지막 숫자가 현재 숫자보다 적으면, 배열 마지막에 현재 숫자를 넣고, 그렇지 않다면, 이분탐색을 통해서 배열에서 현재 숫자보다 크거나 같으면서 가장 작은 숫자를 찾습니다.  그리고 그 숫자 자리에 현재 숫자를 덮어 쓰면, 현재 배열은 증가하는 순서로 되어 있고, 추가된 숫자는 현재의 최장 증가하는 부분 수열의 길이를 증가시키는 것이고, 덮어쓴 숫자는 그 숫자를 통해서 최장 증가하는 부분 수열 길이가 되는 경우를 반영합니다.

 

예를 들어서 2 6 8 9 3 4 5 7 이라는 수열이 있다고 해보죠.  동적 프로그래밍으로 한다면 다음과 같은 표가 만들어질겁니다.

 

	2	6	8	9	3	4	5	7
\(dp_i\)	1	2	3	4	2	3	4	5

 

답은 5가 됩니다.

 

이것을 배열을 이용해서 하면 다음과 같이 됩니다.  먼저 첫번째 수 2를 추가합니다.

 

2

 

다음으로는 6을 추가합니다.  마지막 수인 2보다 6은 크니까 배열의 마지막에 추가합니다.

 

2

6

 

이제, 8, 9를 추가합니다.  8은 6보다 크고, 9도 8보다 크니 배열 뒤에 차례로 추가됩니다.

 

2

6

8

9

 

다음은 3을 추가해야 합니다.  3은 9보다 작으므로, 현재 배열 숫자중 3보다 크거나 같으면서 가장 작은 수인 6을 선택해서 해당 자리에 덮어씁니다.

 

2

3

8

9

 

다음 4도 마찬가지로 9보다 작으므로 배열중 4보다 크거나같으면서 가장 작은 수인 8을 덮어씁니다.

 

2

3

4

9

 

5도 9보다 작으므로 배열중 9가 선택되고 그 자리를 덮어씁니다.

 

2

3

4

5

 

마지막으로 7은 5보다 큰 숫자이므로 배열 뒤에 추가됩니다.

 

2

3

4

5

7

 

이렇게 해서 자연스럽게 최장 증가하는 부분 수열의 갯수는 현재 배열의 크기가 됩니다.  배열에 있는 현재의 데이터는 아쉽게도 최장 증가하는 부분 수열은 아닙니다.  제가 설명한 예제에서는 최장 부분 수열이 되었지만, 대부분 경우에는 최장 부분 수열이 배열값이 되지는 않습니다.  별도로 배열을 만들어서 표시해주어야 합니다.

 

동적 프로그래밍으로 할 경우 최선이 되어도 \(O(N^2)\)이 되지만, 이 방법으로 하면, 최악이라고 해도 \(O(N Log N)\)이 됩니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------------
//  baekjoon #1365 - Tangled Lines
//    - by Aubrey Choi
//    - created at 2019-08-07
//----------------------------------------------------------------------------------------
#include <stdio.h>
#include <algorithm>

int main()
{
  int n, s, cur=0, i; static int v[1000000];
  scanf("%d", &n);
  for(i=0;i<n;i++)
  {
    scanf("%d", &s);
    if(!cur||v[cur - 1] < s) v[cur++]=s;
    else *std::lower_bound(v, v + cur, s)=s;
  }
  printf("%d\n", n-cur);
}