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

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

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

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

Tip

•

특정 인덱스 i를 기준으로 가장 긴 바이토닉 부분 수열 길이 구하기

◦

i 기준으로 가장 긴 증가하는 부분 수열 길이 + 가장 긴 감소하는 부분 수열 길이 - 1

•

가장 긴 증가 / 감소하는 부분 수열 길이는 다이나믹 프로그래밍을 활용해서 구하자!

풀이 소스 코드

import sys
si = sys.stdin.readline
# n과 수열 입력
n = int(si())
array = list(map(int, si().split()))
# 증가, 감소, 바이토닉 부분 수열 길이를 담을 DP 테이블
up = [1] * n # 증가
down = [1] * n # 감소
dp = [1] * n # 바이토닉
# 증가하는 부분 수열 길이 계산
for i in range(n):
for j in range(i):
if array[i] > array[j]:
up[i] = max(up[i], up[j] + 1)
# 감소하는 부분 수열 길이 계산
for i in range(n - 1, -1, -1):
for j in range(n - 1, i, -1):
if array[i] > array[j]:
down[i] = max(down[i], down[j] + 1)
# 증가하는 부분 수열 길이와 감소하는 부분 수열 길이를 더해 바이토닉 수열 길이 계산
for i in range(n):
dp[i] = up[i] + down[i] - 1
# 출력
print(max(dp))
Python