[파이썬] 백준 4198번: 열차정렬

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

4198번: 열차정렬

 

문제

에린은 엔지니어이자, 기차를 운전하는 기관사입니다. 또한 그녀는 각 열차를 구성하는 차량을 배열하는 일도 합니다. 그녀는 차량들을 정렬할 때, 열차의 전면에 가장 무거운 차량을 놓고, 후미로 갈수록 중량이 감소하는 순서로 차량을 넣는 것을 좋아합니다.

불행하게도, 차량을 배열하는 일은 쉽지 않습니다. 기존에 구성된 열차에 다른 차량을 끼워넣는 일은 비실용적이어서 하지 않기에, 한 차량은 오로지 열차의 전면 혹은 후미에만 추가하는 것이 가능합니다.

차량들은 미리 준비된 순서에 따라 역에 도착합니다. 에린은 각 차량이 기차역에 도착할 때, 전면 혹은 후미에 차량을 추가하거나, 차량을 열차에 추가하는 것을 거부할 수 있습니다. 에린이 최종적으로 만든 열차는 가능한 길어야(많은 차량으로 구성되어야)하지만, 그 과정에서 열차는 에린이 배열하고자하는 정렬 순서에 맞아야 합니다.

각 차량이 역에 도착하는 순서대로 차량들의 중량이 주어질 때, 에린이 만들 수 있는 가장 긴 열차배열의 길이(=차량의 수)는 얼마입니까?

입력

첫째 줄에 차량의 수를 나타내는 N (0 <= N <= 2000)이 주어집니다. 이후 N개의 각 줄에는 음이 아닌 차량의 무게가 주어집니다. (단, 서로 다른 두 차량의 무게가 같은 일은 발생하지 않습니다.)

출력

에린이 만들 수 있는 가장 긴 열차의 길이를 출력하세요.

예제 입력 1 복사

3
1
2
3

예제 출력 1 복사

3

 

# LIS(증가하는 부분수열의 길이), LDS(감소하는 부분수열의 길이)를 합하는 문제
# DP(다이나믹프로그래밍)활용
import sys
import bisect
input=sys.stdin.readline

N=int(input())
arr=[]
for _ in range(N):
    a=int(input())
    arr.append(a)

maxx=0
for i in range(len(arr)):
    LIS,LDS=[arr[i]],[-arr[i]]
    for j in range(i+1, len(arr)):
        q=bisect.bisect_left(LIS,arr[j]) # LIS 배열에서 arr[j]가 들어갈 수 있는 자리 찾기
        w=bisect.bisect_left(LDS,-arr[j]) # LDS 배열에서 -arr[j]가 들어갈 수 있는 자리 찾기
        if q:
            if len(LIS)!=q: LIS[q]=arr[j]
            else: LIS.append(arr[j])
        if w:
            if len(LDS)!=w: LDS[w]=-arr[j]
            else: LDS.append(-arr[j])
    maxx=max(maxx,len(LIS)+len(LDS)-1)
print(maxx)