백준 11054 : 가장 긴 바이토닉 부분 수열 (Python)

본문 링크

N=int(input())

a=list(map(int,input().split()))
Reverse=a[::-1]
dp1=[0]*N
dp2=[0]*N

answer=0
for i in range(N):
    for j in range(i):
        if a[i]>a[j] and dp1[i]<dp1[j]:
            dp1[i]=dp1[j]
        if Reverse[i]>Reverse[j] and dp2[i]<dp2[j]:
            dp2[i]=dp2[j]
    dp1[i]+=1
    dp2[i]+=1

dp2.reverse()
for i in range(N):
    answer=max(answer,dp1[i]+dp2[i])
print(answer-1)

📌 어떻게 접근할 것인가?

가장 긴 증가하는 부분 수열 알고리즘을 활용한 문제이다.

바이토닉 부분수열은 증가하거나 감소하는 가장 긴 부분 수열의 길이를 구하는 문제이다.

간단하게 가장 긴 증가하는 부분 수열 알고리즘을 2번 적용시키면된다.

다만 이때 감소하는 부분수열의 길이는 원래 리스트를 역순으로 고친다음에
증가하는 부분 수열로 구한다.

그러면 감소하는 부분수열과 증가하는 부분수열이 만들어지는데

처음에 감소하는 부분수열을 역순으로 구하였기 때문에 증가하는 부분수열과 배열값이 반대이다.
따라서 다시 감소하는 부분수열을 역순으로 고치고

반복문을 통해 answer=max(answer, dp[i]+dp2[i]) 를 통해 가장 긴 증가하면서 감소하는 부분 수열의 길이를 구한다.