🟩 [백준] [Python] [Gold2] 12015번_가장 긴 증가하는 부분 수열 2

문제

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

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

풀이

# 백준 12015번 문제 - 가장 긴 증가하는 부분 수열
n = int(input())
arr = list(map(int, input().split()))
stack = [0]
def binary_search(target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if stack[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return start

for i in arr:
    if stack[-1] < i:
        stack.append(i)
    else:
        stack[binary_search(i, 0, len(stack) - 1)] = i
print(len(stack) - 1) # 0을 빼야하므로 -1

처음 풀었을 때 LIS 알고리즘을 사용할 때 두가지 방법이 있는 줄 몰랐다. 

나는 DP로만 생각하다가 이분탐색을 사용할 것이라고는 생각하지 못해서 풀지 못하였다. 

 

수열의 길이만 구하면 되므로 이분탐색이 가능하다.

스택을 새로 만들어준다. 그리고 스택의 맨 마지막 값이 i 보다 작다면 삽입하고 그렇지 않다면

스택의 인덱스를 찾기 위해 이분탐색을 하고 인덱스의 값을 결과값으로 변경해주면 된다.