백준 - 12738(DP,LIS,이분탐색,bisect)

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

12738번: 가장 긴 증가하는 부분 수열 3

from bisect import bisect_left
import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
dp = []

for i in arr:
    k = bisect_left(dp, i)
    if len(dp) <= k:
        dp.append(i)
    else:
        dp[k] = i

print(len(dp))

LIS로 고통받고 있다가 재미있는 파이썬 built in 모듈을 발견했다.

https://programming119.tistory.com/196

[Python] bisect 사용법👀 / 이분탐색 / 코딩테스트

bisect라는 모듈인데 이진 탐색을 쉽게 구현해주는 함수이다.

from bisect import bisect_left,bisect_right
import sys

arr = [1,2,3,4,5,6,7,8,9,10]

n = int(sys.stdin.readline())

r = bisect_right(arr,n) #n이 arr에서 몇번째에 들어갈지(오른쪽 기준)
l = bisect_left(arr,n) #n이 arr에서 몇번째에 들어갈지(오른쪽 기준

print(r,l)

위 예시를 보면 6을 입력했다고 가정하면 6,5가 출력된다.

 

이제 이걸 dp라는 배열에 조건에 맞게 넣어주는 것이다.

dp 배열에 제일 마지막에 있는 값이 현재까지 최적해 중 가장 큰 값임이 보장된다.

만약 k의 값이 dp의 길이보다 크다면 이는 가장 큰 값이 새롭게 경신된 것이므로 dp의 맨 마지막에 넣는다.

그렇지 않을 기존의 값을 새로운 k값이 대체한다.

최종적으로 만들어진 dp배열의 길이를 출력해주면 정답이다.