문제

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

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

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

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

입력

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

출력

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

풀이

~LIS 설명 생략~

lis와 lds를 모두 구하고 적절히 활용해야 했던 문제. LIS 처음 봤을 때보다 어려웠다.

차량을 끼워넣을 때, 전면과 후미에 끼워넣을 수 있는 형태이다.
차량은 내림차순 형태로 만들 수 있다.
전면에 붙이는 걸 고려한다면 LIS가 될 것이고, 후미에 붙인다면 LDS 형태로 붙일 수 있을 것이다.

처음에는 조건을 잘못 읽어서 전면 혹은 후미에만 붙이는 줄 알았다... 하지만 전면과 후미 모두에 붙일 수 있다.
따라서 LIS와 LDS 모두를 구해야 하는데, 이때 숨겨진(?) 조건이 하나 더있다.
LIS(반대도 가능)를 구성할 때, i번째 차량 번호로 시작한다면 LDS 또한 i번째 차량 번호로 시작해야 한다는 것이다.

아래 예제를 통해 확인해보자.

1 4 3 2 5

해당 입력에서 LIS는 1 3 5, LDS는 4 3 2이다.
그러나 문제의 조건에 따르면 최적해를 이루는 LIS는 4 5, LDS는 4 3 2이다.
만약 i번째 열차를 시작 열차로 선택했다면 반드시 해당 열차의 전면 혹은 후미에만 부착할 수 있기 때문에, 시작하는 원소의 값이 다를 시 최적해를 구성할 수 없다!

최적해의 경우, i 번째 원소를 포함하는 최장 증가 부분 수열에 대해, lis(i)라고 하자. 이때 lis(i)의 길이가 L1이라고 하고, 반대로 최장 감소 부분 수열의 경우 lds(i)라 하고 이때의 길이는 L2라고 해보자.
lis와 lds 모두 공통 원소로 i 번째 원소를 포함하므로 L1+L2-1로 계산해주면 해결할 수 있을 것이다.

코드 구현의 경우 lis 함수 내부에서 수열 구성을 위해 쓰이는 리스트 k에서 인덱스 0번(i번 열차)가 갱신되지 않도록 구성해보았다.

LDS의 경우, 입력을 음수로 바꾼 배열을 추가로 만들어 구현하였다. 우선순위큐에 값을 음수로 넣어주는 거랑 비슷하다.

from bisect import bisect_left

input = open(0).readline

def lis(arr, N, start):
    k = [arr[start]]
    l_k = []
    for i in range(start+1, N):
        idx = bisect_left(k, arr[i])
        if not idx: continue # idx == 0
        if idx == len(k): k.append(arr[i])
        else: k[idx] = arr[i]
        l_k.append(idx+1)
    return max(l_k) if l_k else 1

N = int(input())
arr = [int(input()) for _ in range(N)]
# arr = [*map(int, input().split())] # for test

lis_l = [lis(arr, N, i) for i in range(N)]
drr = [-arr[i] for i in range(N)] # for lds
lds_l = [lis(drr, N, i) for i in range(N)]

ans = 0
for i, j in zip(lis_l, lds_l):
    ans=max(ans, i+j-1)
print(ans)

놀랍게도, dp를 이용한 풀이가 더 빨랐다. 아마 lis와 lds를 한번의 루프안에서 끝낼 수 있어서인 것 같다. 입력값이 2000 이내라서 dp를 이용한 풀이도 가능한 것 같기도...