[알고리즘] 동적 계획법(Dynamic Programming) - 백준 11054번 가장 긴 바이토닉 부분 수열

import sys
input = sys.stdin.readline

n = int(input().rstrip())

seq = list(map(int, input().rstrip().split()))
new_seq = list(reversed(seq))

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

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

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

dp_right = list(reversed(dp_right))

result = []
for i in range(len(dp_left)):
    result.append(dp_left[i] + dp_right[i])

print(max(result) -1)

비슷한 문제

백준 - 11053번 가장 긴 증가하는 부분 수열

https://velog.io/@minidoo/algorithmbaekjoon11053

풀이과정

LIS 를 구하는 것과 결국 같은 문제이다.
S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN 에서 S1 < S2 < ... Sk-1 < Sk 는 11053번과 같이 풀면 되고, Sk > Sk+1 > ... SN-1 > SN 는 역순으로 뒤집어 풀면 결국 같은 문제가 된다.

두 과정에서 나온 배열의 각 원소 값을 합치고 max 값을 구해 1을 빼준다. 1을 빼주는 이유는 SK가 2번 들어가기 때문이다.