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

소스코드

n = int(input())
A = list(map(int, input().split()))
increase = [1] * n
decrease = [1] * n
result = [0] * n
#increase
for i in range(n):
    for j in range(i):
        if A[i] > A[j] :
            increase[i] = max(increase[i], increase[j]+1)
#decrease
for i in range(n-1,-1, -1):
    for j in range(i+1,n):
        if A[i] > A[j] :
            decrease[i] = max(decrease[i], decrease[j]+1)
    result[i] = increase[i] + decrease[i] - 1
print(max(result))

 

바이토닉 수열은 특정 수 기준으로 앞에는 증가, 뒤에는 감소 하는 수열이다.

따라서 증가하는 수열과 감소하는 수열의 dp 를 따로 구해줘야한다.

 

증가하는 수열은 0 부터 i-1 까지 돌면서 i값과 비교하여, j 의 dp + 1 값 중 가장 큰 값을 i의 dp 값으로 저장한다.

감소하는 수열은 i 가 n-1 부터 -1 까지 역으로 돌면서, j는 i+1 부터 n 까지 돈다. 증가 하는 수열에서의 수식과 마찬가지로 구해주면 된다. (역이니깐 감소가 됨)

 

따라서 result [i] 값은 increase[i] + decrease[i] - 1(중복된 자신) 이 되고

max(result) 값이 가장 긴 수열의 길이가 된다.