[백준] 11054번 가장 긴 바이토닉 부분 수열 ★

💡문제접근

• 이전에 포스팅했던 [[백준] 11053번 가장 긴 증가하는 부분 수열]과 [[백준] 11055번 가장 큰 증가하는 부분 수열] 문제를 이미 경험해봐서 그런지 접근하는 부분에 있어서는 엄청 헤매지 않았던 것 같다. 다이나믹 프로그래밍에 대한 문제를 더 풀어보면서 감을 익히고 그 개념이 무엇인지 더 잘 알게 되었다.

💡코드(메모리 : 31256KB, 시간 : 288ms)

import sys
input = sys.stdin.readline

N = int(input())

increase = [1 for _ in range(N)]  # 가장 긴 바이토닉 부분 수열(증가하는)
decrease = [1 for _ in range(N)]  # 가장 긴 바이토닉 부분 수열(감소하는)
dp = [0 for _ in range(N)]
A = list(map(int, input().strip().split()))

for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            increase[i] = max(increase[i], increase[j]+1)

for i in range(N-1, -1, -1):
    for j in range(i+1, N):
        if A[i] > A[j]:
            decrease[i] = max(decrease[i], decrease[j]+1)

for i in range(N):
    dp[i] = increase[i] + decrease[i]
print(max(dp)-1)

💡소요시간 : 27m