백준 11054번: 가장 긴 바이토닉 부분 수열 (Python)

접근

백준 단계별 문제에서 바로 이전 단계인 11053번 가장 긴 증가하는 부분 수열과 비슷한 문제이다.

2021.03.28 - [SW/백준 (Python)] - 백준 11053번: 가장 긴 증가하는 부분 수열 (Python)

백준 11053번: 가장 긴 증가하는 부분 수열 (Python)

다만 다른 점은 증가하는 수열이 아닌 바이토닉 수열(의미는 문제 참조)이기 때문에 증가하다가 감소하는 수열이어야 한다. 이를 해결 하기 위해 앞에서 부터 증가하는 부분 수열을 구할 뿐 아니라 뒤에서 부터 순서로 계산하여 감소하는 수열도 구하여야 한다. 이를 합산하면 답을 구할 수 있다.

코드

import sys

n = int(sys.stdin.readline())
m = [0] + list(map(int, sys.stdin.readline().split())) + [0]
dp1 = [0 for _ in range(n + 2)]
dp2 = dp1[:]
dp = dp1[:]
for i in range(1, n + 1):
    maximum1 = 0
    maximum2 = 0
    for j in range(i):
        if m[j] < m[i]:
            if dp1[j] >= maximum1:
                maximum1 = dp1[j]
        if m[n - j + 1] < m[n - i + 1]:
            if dp2[n - j + 1] >= maximum2:
                maximum2 = dp2[n - j + 1]
    dp1[i] = maximum1 + 1
    dp2[n - i + 1] = maximum2 + 1
for i in range(len(dp1)):
    dp[i] = dp1[i] + dp2[i] - 1
print(max(dp))

더 생각해 볼 것?

...