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

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

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

Problem

• 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.
• 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

조건

• 예를 들어, {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이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

SOL

처음에는 , LIS 구하고 맨 마지막 값 Sk를 기준으로  , 그 뒤에 부분은 LDS (가장 긴 감소 부분수열)을 구하면 되겠다고 생각했다. 하지만, 이럴러면, LIS의 마지막 값 중에, 가장 큰 친구로 끝나는 경우를 찾아야한다. 

그리고, 그 값을 시작으로 또 LDS를 다시 돌아야함. 구현은 가능하겠지만, 상당히 번거로운 작업이 필요할 거 같다.

배열 자체를 뒤집거나, 배열을 거꾸로 돌아주는 방법이 떠올랐음. (LIS의 논리를 그대로 사용 가능하다)

• S1<S2<S3<...SK
• Sn<Sn-1...<Sk 

#bottom up
N = int(input())
seq=list(map(int,input().split()))
DP=[1]*N
DP_r=[1]*N
for i in range(N):
    for j in range(i):
        if seq[i]>seq[j]:
            DP[i] = max(DP[i],DP[j]+1)

for i in range(N-1,-1,-1):
    for j in range(N-1,i,-1):
        if seq[i]>seq[j]:
            DP_r[i] = max(DP_r[i],DP_r[j]+1)

ans=[0]*N
for i in range(N):
    ans[i] = DP[i] +DP_r[i]

print(max(ans)-1)

• 배열이 뒤집어 준다면, ans부분에서 , 인덱스를 잘 맞춰줘야한다. 왜냐하면, LIS의 DP table의 인덱스가, 배열이 뒤집히면서, DP table의 인덱스도 뒤집히기 때문에, DP_r table은 거꾸로 더해줘야함.

  

  DP,DP_r의 값을 하나씩 나타내어봤음.