[백준] / [Python] / [12015] 가장 긴 증가하는 부분 수열 2

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

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

---

문제

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

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

입력

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

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

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

---

앞서 풀었던 가장 긴 증가하는 부분수열 풀이 방식은 DP를 활용한 것이고 이를 그대로 적용한다면 시간초과 오류를 출력한다. 따라서 이분 탐색을 활용하여 풀이해야 한다.

이 방법은 수열 A를 처음부터 끝까지 for문을 돌면서 조건에 만족하면 LIS리스트에 추가하는데, LIS 원소들은 A의 "가장 긴 증가하는 부분 수열"을 만족하지는 않지만 리스트의 길이를 만족한다는 점을 생각해야 한다.

 

[10, 20, 10, 30, 25, 50]을 예로 들자면,

처음 LIS = [10] 이다. 이후 for문을 돌며 LIS를 하나씩 채워 나가는 것이다. 다음 원소인 20은 LIS의 마지막 원소인 10보다 크므로 LIS에 추가해 준다.

 

다음 원소인 10은 LIS의 마지막 원소인 20보다 작거나 같으므로, 이분 탐색을 통하여 넣어줄 인덱스를 찾는다. (10보다 크거나 같은 원소를 처음 만나는 위치의 인덱스) 인덱스는 0이므로 LIS[0]에 10을 넣어준다.

 

다음 원소 30은 LIS의 마지막 원소인 20보다 크므로 LIS에 추가해 준다.

 

다음 원소 25는 LIS의 마지막 원소 30보다 작거나 같으므로, 이분 탐색을 통하여 넣어줄 인덱스를 찾는다.

현재 LIS=[10, 20, 30] 의 왼쪽부터 탐색하여 30의 자리인 인덱스 2를 LIS[2] = 25로 변경한다.

 

인덱스를 찾아서 변경해주는 이유는 다음 원소를 탐색할 때, LIS[-1]보다 더 작은 원소를 대입해야 다음에 더 많은 수를 담을 수 있기 때문이다. ([10, 20, 60, 30, 40] 의 경우 변경하지 않고 넘어간다면 어떻게 될 지 생각해보자.)

 

또한, 앞서 설명하였던 LIS 원소들은 A의 "가장 긴 증가하는 부분 수열"을 만족하지는 않지만 리스트의 길이를 만족한다는 점을 생각해야 한다는 부분은 [10, 20, 30, 15, 50] 의 경우 가장 긴 증가하는 부분 수열은 [10, 20, 30, 50] 이지만 위 방식을 진행하면 [10, 15, 30, 50]을 출력하기 때문이다. 하지만 목적인 LIS의 길이는 똑같이 출력한다.

 

참고

 

import sys
input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))

LIS = [nums[0]]

for num in nums:
    if LIS[-1] < num:
        LIS.append(num)
    else:
        start = 0
        end = len(LIS)-1        
        while start <= end:
            mid = (start+end)//2
            
            if LIS[mid] < num:
                start = mid + 1
            else:
                end = mid - 1
        
        LIS[start] = num
        
print(len(LIS))