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

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

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

n = int(input())

num = list(map(int, input().split()))
num_reverse = list(reversed(num))

dp = [1 for i in range(n)]
dp_r = [1 for i in range(n)]

for i in range(n):
    for j in range(i):
        if num[i]> num[j]:
            dp[i] = max(dp[i],dp[j]+1)
        if num_reverse[i] > num_reverse[j]:
            dp_r[i] = max(dp_r[i],dp_r[j]+1)

answer = [0 for i in range(n)]
for i in range(n):
    answer[i] = dp[i] + dp_r[n-1-i]-1


print(max(answer))

 

이거 진짜 새로운거 배웠다.

 

https://seohyun0120.tistory.com/entry/%EB%B0%B1%EC%A4%80-11054-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EB%B0%94%EC%9D%B4%ED%86%A0%EB%8B%89-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-%ED%92%80%EC%9D%B4

[백준] 11054 가장 긴 바이토닉 부분 수열 풀이 - (python 파이썬)

이분 블로그를 참고했다.

 

이문제를 풀때 중요한것 또 메모지에이션 

전에 있던 값 들 중 길이가 가장 긴것을 기반으로 그 값을 더해서 하는것

 

이게 중요하다. 잘 알아두자.