[Python/파이썬] 백준 11054번: 가장 긴 바이토닉 부분 수열

문제

 

풀이

가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열을 구하면 된다.

(부분 수열 시리즈를 풀었다면 쉽게 풀 수 있다.)

 

코드

import sys
input = sys.stdin.readline


n = int(input())
arr = list(map(int, input().split()))

dpMax = [1] * n
dpMin = [1] * n

for i in range(1, n):
    for j in range(i):
        if arr[i] > arr[j]:
            dpMax[i] = max(dpMax[i], dpMax[j] + 1)

for i in range(n - 1, -1, -1):
    for j in range(i, n):
        if arr[i] > arr[j]:
            dpMin[i] = max(dpMin[i], dpMin[j] + 1)

print(max([a + b for a, b in zip(dpMax, dpMin)]) - 1)

 

마무리

부분 수열 문제는 이제 어느 정도(?) 마스터한 거 같다.