가장 긴 증가하는 부분 수열 3

import sys
from bisect import bisect_left
input = sys.stdin.readline


def BOJ12738():
  N = int(input())
  A = list(map(int, input().split()))

  dist = [-1000000001]
  index = [0] * (N + 1)

  for i in range(len(A)):
    num = A[i]
    if dist[-1] < num:
      dist.append(num)
    else:
      index[i] = bisect_left(dist, num)
      dist[index[i]] = num

  max_length = len(dist) - 1
  print(max_length)


BOJ12738()

 

접근 방법 

0. 거리 배열을 하나 두자 

1. 거리 배열의 제일 마지막 값보다 크면 증가하는 부분 수열은 증가하게 된다

2. 제일 마지막 값보다 크지 않다면 기존의 증가하는 수열중에서 값을 갱신 시켜주어야 한다. (이때 index를 찾을때 이진탐색 사용)

3. 2번 과정이 있어야 하는 이유는
     1 5 10 4 6 의 배열이 들어오게 된 경우
     1 5 10 다음에
     1 4 10 그리고
     1 4 6 으로 수정이 되어야 이후의 입력 배열에서 값을 비교하여 업데이트가 가능하기 때문이다

4. 배열의 길이를 출력해주면 끝

 

 

장애물 이였던 것 

0. 범위가 커서 일반 dp로 접근하면 안된다

1. 이진 탐색 코드를 직접 짰던걸로 구현했었는데 bisect_left로 변경하였다. 지금 생각해보면 직접 구현한 이진 탐색 코드도 답을 구하는데 있어서 틀린건 아니었던것 같다

 

 

 

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

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