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

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

가장 긴 증가하는 부분수열 문제를 풀고

이건 반대로 감소하는 부분 수열의 최대 값을 더해서

합 한 다음에 1을 빼면 되지 않을까 생각해서 풀었는데,

 

계속 틀렸다고 나와서 아예 다른 방법으로 풀다가 맞긴 맞았다.

 

import sys
input=sys.stdin.readline
N=int(input())
ary=list(map(int,input().split()))
dp=[1]*N
dp2=[1]*N
for i in range(N):
    for j in range(i):
        if ary[i]>ary[j]:
            dp[i]=max(dp[i],dp[j]+1)

for i in range(N-1,-1,-1):
    for j in range(N-1,i,-1):
        if ary[i]>ary[j]:
            dp2[i]=max(dp2[i],dp2[j]+1)

for i in range(N):
    dp[i]+=dp2[i]-1

print(max(dp))

근데 원래 방법으로 푼 사람이 있어서 봤는데

그냥 내가 코딩을 잘 못 했던것..

 

ㅎ,, 근데 어떻게 예제가 들어 맞았던 건지는 모르겠지만..

어쨌든 for문을 반대로 돌리는것만 제대로 했어도 금방 풀었을텐데,,

 

아쉬운 문제였다.