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

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

11054번: 가장 긴 바이토닉 부분 수열

아이디어

•  dp 배열 2개를 만들어 각 지점에서 우측 좌측 '가장 긴 증가하는 수열' 문제에서 사용한 점화식을 적용
• 두 dp배열을 모두 만들어준 후 합쳐주어 바이토닉 부분 수열의 길이를 구함

구현

import sys

input = sys.stdin.readline

n = int(input())

s = list(map(int, input().split()))

dp_left = [1]*n
dp_right = [1]*n

for i in range(1, n):
    for j in range(i):
        #왼쪽 dp 
        if s[i] > s[j]:
            dp_left[i] = max(dp_left[i], dp_left[j]+1)
        #오른쪽 dp
        if s[n-1-i]>s[n-1-j]:
            dp_right[n-1-i] = max(dp_right[n-1-i], dp_right[n-1-j]+1)

dp = [0]*n

for i in range(n):
    dp[i] = dp_left[i] + dp_right[i]

# 중복되게 셈을 한 수 빼기
print(max(dp)-1)

마무리

• 이게 어떻게 풀어야지 감은 잡혔는데 한 번에 딱 구현하지는 못했다..
• 조금만 더 실력을 키우면 10분 안에 풀어버릴 만한 문제가 아닐까