[백준 알고리즘] 11054번: 가장 긴 바이토닉 부분 수열 (Python / 파이썬)

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

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

코드

N = int(input())
a = list(map(int,input().split()))
dp_up = [0]*N
dp_down = [0]*N
for i in range(N):
    for j in range(i):
        if a[i] > a[j] and dp_up[i] < dp_up[j]:
            dp_up[i] = dp_up[j]
    dp_up[i] += 1
    for j in range(N-1,-i-1,-1):
        if a[-i-1] > a[j] and dp_down[-i-1] < dp_down[j]:
            dp_down[-i-1] = dp_down[j]
    dp_down[-i-1] += 1
mx = 0
for i in range(N):
    if dp_up[i] + dp_down[i] > mx:
        mx = dp_up[i] + dp_down[i]
print(mx-1)

풀이

바이토닉 순열은 즉 어떤 수를 기준으로 왼쪽에서 시작해도 증가수열, 오른쪽에서 시작해도 증가수열인 순열을 뜻합니다.
고로 리스트 dp_up에는 왼쪽에서 시작한 경우의 부분순열의 길이를, dp_down에는 오른쪽에서 시작한 경우의 부분순열의 길이를 각각 저장해주었습니다.
예제 1번의 순열 [1, 5, 2, 1, 4, 3, 4, 5, 2, 1]을 예로 들면 아래와 같습니다.
dp_up = [1, 2, 2, 1, 3, 3, 4, 5, 2, 1]
dp_down = [1, 5, 2, 1, 4, 3, 3, 3, 2, 1]
가장 긴 바이토닉 부분수열을 찾아야하기 때문에 두 리스트의 같은 인덱스끼리 더했을 때 가장 큰 인덱스를 분기점으로 하여 가장 긴 바이토닉 부분수열의 길이를 구할 수 있습니다.
위의 경우는 dp_up[7] + dp_down[7] = 8로 가장 큰 값이네요.
이때 두 수열의 길이를 합치면 분기점을 두번 더한 값이 나오니
최대값에서 1을 뺀 값을 출력하여 줍니다.