[백준] 12738번 - 가장 긴 증가하는 부분 수열 3 (파이썬)

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

# 가장 긴 증가하는 부분 수열 3
import sys
import bisect
input = sys.stdin.readline
N = int(input())
arr = list(map(int, input().split()))

result = [arr[0]]

for i in range(1, N):
    if arr[i] > result[-1]:
        result.append(arr[i])
    else:
        index = bisect.bisect_left(result, arr[i])
        result[index] = arr[i]

print(len(result))

 

이진탐색, bisect

1. 전체 리스트를 돌면서

    - result의 마지막 원소보다 크면 append를 해준다

    - 작으면 bisect_left를 이용하여 해당 인덱스의 값을 바꿔준다

2. result배열의 길이를 출력

 

가장 긴 증가하는 부분 수열 2와 똑같은 풀이로 풀었다.

 

가장 긴 증가하는 부분 수열 2: https://2hs-rti.tistory.com/38

[백준] 12015번 - 가장 긴 증가하는 부분 수열 2 (파이썬)

가장 긴 증가하는 부분 수열 (DP풀이) : https://2hs-rti.tistory.com/37

[백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬)