가장 긴 증가하는 부분 수열 4 [백준 14002] - python

 

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

def BOJ14002():
  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)
      index[i] = len(dist) - 1
    else:
      index[i] = bisect_left(dist, num)
      dist[index[i]] = num

  max_length = len(dist) - 1
  print(max_length)
  answer = []
  for i in range(N, -1, -1):
    if index[i] == max_length:
      answer.append(A[i])
      max_length -= 1

  print(*(reversed(answer)))


BOJ14002()

 

접근 방법 :

0. index 전용 배열을 추가하자

1. 최대 거리를 업데이트 하는 형식으로 진행할 것이다

2. 비교값이 거리 배열의 마지막 값보다 크면 추가, 작으면 기존의 거리 배열중 자기보다 큰 첫 번째 값을 찾아 업데이트 해준다(이진 탐색 사용)

3. 업데이트 시마다 비교값이 들어가는 index값을 index 전용 배열에 추가해준다.

4. 1 5 10 4 6 7 을 예로 들어보자 
     1 5 10 까지는 문제없을 것이다.  
     1 4 10 이 되고
     1 4 6 
     1 4 6 7 
  

     거리 배열

       1 4 6 7

     인덱스 전용 배열 

       1 2 3 2 3 4 

 

5. 거꾸로 탐색 and 출력 인덱스 값을 하나씩 줄이면서 맞는 위치의 값을 정답 배열에 추가하고 출력하면 끝!

 

장애물 이였던 것 :

0. 가장 긴 증가하는 부분 수열을 출력하는 내용이 너무 어려웠다. 도저히 방법이 떠오르지 않았다.

1. 0번의 해결책으로 index 전용 배열을 하나 추가로 두었다.

2. 인덱스를 업데이트 하는 로직에서 많이 헤매었다

 

 

 

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

14002번: 가장 긴 증가하는 부분 수열 4