[백준] 12015 : 가장 긴 증가하는 부분 수열 2 python

 

https://velog.io/@ledcost/%EB%B0%B1%EC%A4%80-12015-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%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-%EA%B3%A8%EB%93%9C2-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89

 

위 포스트를 참고해서 문제를 풀었다.

 

우선 arr라는 리스트에 입력받은 값들을 저장한다.

 

그리고 res라는 리스트를 만들고 arr[0]를 저장한 뒤에,

arr에 저장된 값과 res의 마지막값을 비교하며 더 클 경우에는 res에 추가하고

작거나 같을 경우에는 res안에서 적절한 위치를 찾아서 넣어준다.

 

이를 끝까지 반복하면 res의 원소들이 최대길이증가수열이라는 건 보장할 수 없지만

res의 원소개수가 최대길이증가수열의 길이가 되기 때문에 이 문제에 적용할 수 있는 것이다.

 

 

 

 

n = int(input())
arr = list(map(int,input().split()))
res = [arr[0]]

for x in arr:
	# res의 마지막 원소보다 크다면 바로 이어붙임
    if res[-1]<x:
        res.append(x)
        
    # 그렇지 않다면 res를 이분탐색하면서 x가 들어갈 적절한 위치를 찾음
    else:
        start = 0
        end = len(res)
        while start<end:
            mid = (start+end)//2
            # res는 항상 정렬된 상태이기 때문에 res[mid]보다 크면 더 뒤쪽을 탐색
            if res[mid]<x:
                start = mid+1
            else:
                end = mid
        res[end] = x
print(len(res))