[Python] 백준 14003번: 가장 긴 증가하는 부분 수열 5

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

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

 

import sys
import bisect
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

if __name__ == '__main__':
    N = int(input())
    nums = list(map(int, input().split()))

    stack = []
    stackLength = 0

    # stack에서의 인덱스를 저장
    dp = [0]*N

    # 기본 LIS
    for i in range(N):
        n = nums[i]
        minBiggerIndex = bisect.bisect_left(stack, n)

        if minBiggerIndex == stackLength:
            stack.append(n)
            stackLength += 1
        else:
            stack[minBiggerIndex] = n

        dp[i] = minBiggerIndex

    print(stackLength)

    # DP의 특정 값에서 가장 마지막에 있는 원소가 정답이다.
    # 가장 마지막으로 Replace했다는 것을 의미하기 때문이다.
    # 이것을 (stack의 마지막 인덱스 ~ 0)까지 진행하면 된다.
    toPrint = []
    for i in range(N-1, -1, -1):
        if dp[i] == stackLength - 1:
            toPrint.append(nums[i])
            stackLength -= 1
    print(*reversed(toPrint))

 

LIS 기본에서 살짝만 응용한 문제이다. LIS를 O(NlogN)으로 푸는 것은 다음 링크를 참고하자. https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-12015%EB%B2%88-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-2

 

LIS에서는 모든 원소에 대해 stack에서 이분탐색을 하고, stack에서의 인덱스를 얻는다. 우리는 이 인덱스들을 모두 저장하여 활용한다. 사실 설명은 주석에 다 달아놓아서 코드를 참고하자.

 

마지막으로, 아래는 문제를 풀면서 도움이 되었던 반례들이다.

 

6
10 20 10 30 15 50

11
1 2 999 1000 13 14 15 16 3 4 5

3
10 11 9

9
3 -8 2 -1 -5 4 0 6 0

9
-81 -35 22 -45 27 -27 54 -35 -8

9
5 88 40 -25 -24 99 5 13 -15

5
34 -43 32 32 -33

9
44 -60 37 93 6 6 -73 15 93