[알고리즘] 백준 11054 파이썬 - 가장 긴 바이토닉 부분 수열

 

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

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

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

 

문제풀이

n=int(input())
a=list(map(int,input().split()))

#01
plus= [1 for i in range(n)]
for i in range(n):
    for j in range(i):
        if a[i]>a[j]:
            plus[i]=max(plus[i],plus[j]+1)
#02
minus=[1 for i in range(n)]
for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
        if a[i]>a[j]:
            minus[i]=max(minus[i],minus[j]+1)
#03
ans=[0]*n
for i in range(n):
    ans[i]=plus[i]+minus[i]-1
print(max(ans))

증가하는 수열 + 감소하는 수열 -(공통 max 값)을 통해 문제를 해결하였다.

- #01 : 0부터 n-1까지 i의 값이 증가하며, j는 그 값에 따라 i-1까지만 증가한다.

           즉 쉽게 말해, i까지 이동했을 때 그 전 값이 i보다 작다면 

           plus[i]값에 변동을 주어 최종적으로, 그 자릿수에서 얻을 수 있는

           가장 긴 증가하는 수열의 길이를 얻는 것이다.

- #02 : 이번에는 위 #01의 풀이를 거꾸로 뒤집어 똑같이 증가하는 수열의

           길이를 찾지만, 뒤집었기에 감소하는 수열의 길이를 구한 것이다.

- #03 : 답을 찾기 위해 "증가하는 수열의 길이"+"감소하는 수열의 길이" -1(max값)을

           해준 값 중에 가장 큰 값을 출력해준다.

 

예시)

10
1 5 2 1 4 3 4 5 2 1

증가하는 수열 : 1 2 3 4 5

감소하는 수열 : 5 2 1

-> 5가 2번 나오기에 둘의 길이를 더하고 1을 빼준 "7"이 답이다.