[백준] 가장 긴 바이토닉 부분 수열

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

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

다이나믹 프로그래밍을 사용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

수열이 주어질 때, 그 수열안의 바이토닉 수열중 길이가 가장 긴 것을 return해야 합니다. 이 때, 바이토닉 수열이란 S(1) < S(2) < ... S(k-1) < S(k) > S(k+1) > ... S(N-1) > S(N)의 조건을 만족하는 수열입니다. 

 

예시를 하나만 첨부하면, [1,2,3,7,5,4,1]은 7을 기준으로 생각해보면 왼쪽으로도 감소하고, 오른쪽으로도 감소하므로 바이토닉 수열이라고 할 수 있습니다. (바이토닉 수열이 전체 수열에서 연속적일 필요는 없습니다)

 

<Solution>

사실 이전 문제로 

https://life318.tistory.com/95

[백준] 가장 긴 증가하는 부분 수열

이 문제에서 증가하는 부분수열에 대해 n^2의 time complexity로 문제를 해결하는 방법을 살펴 보았습니다. 

 

이 문제도 마찬가지로 위와 같은 방법을 사용하는데, 해당 과정을 두번 반복해야 한다는 부분만 다릅니다. 그림으로 살펴보면,

위와 같습니다. 

 

추가적인 예시를 설명해보면, 

1 5 2 1 4 3 4 5 2 1

의 수열에서 위에 색칠한 5를 기준으로 생각해보면, 이 수열에서 5를 포함하는 가장 긴 증가하는 부분수열은 1, 2, 3, 4, 5로 5의 길이를 가지고, 

 

이 수열을 뒤집은

1 2 5 4 3 4 1 2 5 1

에서 5를 포함하는 가장 긴 증가하는 부분수열은 1, 2, 5로 3의 길이임을 알 수 있습니다. 

따라서 가장 긴 바이토닉 부분수열은 3+5-1인 7이 됩니다(-1을 하는 이유는 5가 두번 포함되었기 때문)

 

실제 구현은 아래와 같습니다.

import sys

N = int(sys.stdin.readline().rstrip())
seq = list(map(int, sys.stdin.readline().rstrip().split()))

dp1 = [0] * N
dp1[0] = 1
for i in range(1, N):
    tmp = 0
    for j in range(i):
        if seq[j] < seq[i] and tmp < dp1[j]:
            tmp = dp1[j]
    dp1[i] = tmp+1

dp2 = [0] * N
dp2[0] = 1
rev_seq = seq[::-1]
for i in range(1, N):
    tmp = 0
    for j in range(i):
        if rev_seq[j] < rev_seq[i] and tmp < dp2[j]:
            tmp = dp2[j]
    dp2[i] = tmp+1

ans = 0
for i in range(N):
    tmp = dp1[i] + dp2[N-1-i] -1
    if ans < tmp:
        ans = tmp
print(ans)