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

 

호주에서 주로 철광석 운반에 사용하는, 길이가 무려 7.3km인 세상에서 가장 긴 기차라고 한다.

문제는 아래 링크에 :

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

12015번: 가장 긴 증가하는 부분 수열 2

 

이 알고리즘의 원리는 다음과 같다.

 

---

 

가장 긴 증가하는 부분 수열을 저장할 리스트를 하나 만든다.

 

그리고 주어진 입력값을 순차적으로 순회하며 리스트를 갱신하는데, 아래 과정에 따른다.

• 현재 값 n이 리스트의 최댓값보다 크면, 수열이 증가함이 보장된다. 그러므로 리스트의 마지막에 n을 append 해준다.
  
  
• 현재 값 n이 리스트의 최댓값과 같거나 작다면, 수열이 증가하지 않는다.
  
  
  1. 기존에 존재하던 리스트의 길이가 현재까지 정답(가장 긴 증가하는 부분수열의 길이)인 것은 보장된다.
  2. n에서 시작하여 새로운 정답이 발생하기 위해서는 n의 앞에 있는 n보다 작은 숫자의 개수 + n의 뒤에 오는 n보다 큰 숫자의 개수가 현재 존재하는 수열의 길이보다 길어져야 한다.
  3. 이때, 기존 수열에서 n과 같거나 작은 수들 중, n과 가장 가까운 값에 덮어쓰는 방법을 쓰면
     계속 순회하며 루틴을 실행했을 때에도 위의 2번 조건을 만족하게 되므로
     마지막까지 순회했을 때 리스트의 길이가 최장 길이가 된다.
  4. n과 가장 가까운 값을 찾는 시간을 줄이기 위해, 리스트에서 이분 탐색을 한다.
     리스트는 오름차순으로 정렬되어 있음이 보장되므로, 이분 탐색이 가능하다.

---

 

그러나 위의 과정에서 기존 값을 덮어쓰기 때문에, 리스트가 정답 수열의 값을 가진다는 보장은 없다.

 

정답 수열을 구하는 방법이 분명 있을텐데, 생각하기로는 아래 방법 정도가 있을 거라고 추정해 보았다.

 

• 최댓값보다 작은 n이 나왔을 때, 기존 리스트에서 n보다 작은 값들을 복제하여 새로운 리스트로 만든다.
  
  
• 이후 각 리스트마다 비교를 진행한다.
  
  
• 마지막까지 순회했을때 생성된 리스트들 중 가장 긴 리스트가 정답 수열이다.
  정답 수열은 2개 이상이 나올 수 있다.

 

코드 :

from bisect import bisect_left
def main():
    N = int(input())
    inputs = list(map(int, input().split()))

    arr = []
    arr.append(inputs[0])

    for i in range(1, N):
        n = inputs[i]
        if arr[-1] < n:
            arr.append(n)
        else:
            arr[bisect_left(arr, n)] = n

    print(len(arr))

main()