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

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

 

# 풀이과정

1. DP로 각 지점에서의 증가길이를 찾는다
2. DP로 각 지점에서의 감소길이를 찾는다. (수열의 뒤에서부터 거꾸로 증가하는 것으로 찾으면 쉬움)
3. 두 값의 합이 가장 큰 지점이 중앙임
4. 그 값에서 1을 빼서 출력하면 그것이 최장 바이토닉수열 길이임

 

[DP를 이용한 코드 - 성공]

# ex_11054
import sys

n = int(sys.stdin.readline())   # 길이
nums = list(map(int,sys.stdin.readline().split()))  # 수열
increase = [1 for _ in range(n)]
decrease = [1 for _ in range(n)]

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

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

for i in range(n):
    increase[i]=increase[i]+decrease[i]

print(max(increase)-1)

 

처음에는 시간복잡도를 고려해서 이분탐색으로 하려고 했는데, 주어지는 최대 수열의 길이도 1000으로, 그렇게 길지 않기에 시간초과가 날 걱정도 없고, 수열 자체를 구하는것이 아니라 길이를 구하는 문제라서 그냥 2중 for문을 사용하여 풀었다.