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

문제

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

풀이

가장 긴 증가하는 부분 수열 문제를 응용하면 수월하게 해결할 수 있습니다.
위 문제는 증가하는 부분 수열 문제만 고려하면 됐지만, 이 문제는 감소하는 부분 수열까지 고려해야 합니다.

처음엔 증가하는 부분 수열을 구해줍니다.

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

여기까진 전 문제와 동일합니다.
이제 감소하는 부분 수열을 구해줘야 하는데, 이를 구하기 위해서 입력된 수열을 뒤집어 계산하면 됩니다.

reverse = arr[::-1]
for i in range(1,n):
	for j in range(i):
		if reverse[i] > reverse[j]:
        	dp_l[i] = max(dp_l[i], dp_l[j]+1)

예제를 이용해 결과를 확인해봅시다.

10
1 5 2 1 4 3 4 5 2 1

증가하는 부분 수열
1 5 2 1 4 3 4 5 2 1
감소하는 부분 수열
1 5 2 1 4 3 4 5 2 1

[1, 2, 2, 1, 3, 3, 4, 5, 2, 1]
[1, 5, 2, 1, 4, 3, 3, 3, 2, 1]

즉, "1 5 2 1 4 3 4 5 2 1"이 가장 긴 바이토닉 부분 수열이 됩니다.

증가하는 부분 "1,2,3,4,5"와 감소하는 부분 "5,2,1"을 합쳐주면 최대 길이가 나오게 됩니다.

여기서 주의해야할 점은 증가하는 부분의 마지막에 있는 5와 감소하는 부분의 5는 겹치기 때문에 이 둘을 합친 후 -1을 해줘야 값이 올바르게 나옵니다.

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))
reverse = arr[::-1]

dp_r = [1] * n
dp_l = [1] * n
res = [0] * n

for i in range(1,n):
    for j in range(i):
        if arr[i] > arr[j]:
            dp_r[i] = max(dp_r[i], dp_r[j]+1)
        if reverse[i] > reverse[j]:
            dp_l[i] = max(dp_l[i], dp_l[j]+1)

for i in range(n):
    res[i] = dp_r[i] + dp_l[n-i-1] - 1

print(max(res))