(백준 알고리즘 문제풀이) 12738번 가장 긴 증가하는 부분 수열 3

문제

 

문제 링크

 

문제 접근

• 백준 12015번  과 다른 점은 배열의 값의 범위이다. -1,000,000,000 ~ 1,000,000,000
• 따라서 dp[0]의 초기 값을 -1,000,000,001로 지정해주어야 한다.
• 시간복잡도 O(N logN)인 binary search를 사용해야 한다.

코드

 

import sys

N = int(sys.stdin.readline())
seq = list(map(int, sys.stdin.readline().split()))

dp = [-1000000001]
for i in range(N):
    start = 0
    end = len(dp) - 1
    while start <= end:
        mid = (start + end) // 2
        if dp[mid] < seq[i]:
            start = mid + 1
        else:
            end = mid - 1

    if start >= len(dp):
        dp.append(seq[i])
    else:
        dp[start] = seq[i]

print(len(dp)-1)

느낀점

이전 11055번과 조건이 바뀐것이기때문에 그 조건에 맞는 구현을 적용시키는 것을 찾는 것에 생각을 할 수 있느 문제였다.