[백준] 11054 파이썬

문제

---

• 백준 11054 (골드 4)

백준 11054

수열이 특정 수까지 계속 증가했다가 다시 감소한다면 그 수열을 바이토닉 수열이라고 한다.
수열 a가 주어질 때, 그 수열의 부분 수열중에서 가장 긴 바이토닉 수열의 길이를 구하는 문제였다.

내 코드

---

과거에 풀었던 문제라서 쉽게 다시 풀 수 있었다.
dp를 활용하여서 문제를 접근하였다.
우선 수열 a를 탐색하면서 자신을 포함하는 가장 긴 증가하는 부분 수열의 길이를 dp1 리스트에 업데이트해주었다.
다음으로는 a의 순서를 뒤집어 자신을 포함하는 가장 긴 감소하는 수열의 길이를 dp2 리스트에 업데이트해주었다.
그리고 두 수열을 더해서 그중 최대값을 찾아서 가장 긴 바이토닉 수열의 길이를 구하였다.

import sys
input = sys.stdin.readline

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

dp1 = [1] * n
dp2 = [1] * n

for i in range(1, n):
    for j in range(i):
        if a[j] < a[i]:
            dp1[i] = max(dp1[i], dp1[j] + 1)

a.reverse()
for i in range(1, n):
    for j in range(i):
        if a[j] < a[i]:
            dp2[i] = max(dp2[i], dp2[j] + 1)
dp2.reverse()

ans = 0
for i in range(n):
    ans = max(ans, dp1[i] + dp2[i] - 1)
print(ans)