[python/백준/DP] 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가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

풀이

바이토닉 수열을
1 3 5 4 3 2 이런식으로 계단식으로 내려가는 수열로 생각했는데

1 3 5 7 9 8 9 6 5 2
이 케이스에서도 되는거였다.

주어진 수열 : [1, 3, 5, 7, 9, 8, 9, 6, 5, 2]
증가하는 수열 길이 : [1, 2, 3, 4, 5, 5, 6, 4, 3, 2]
감소하는 수열 길이 : [1, 2, 2, 4, 5, 4, 4, 3, 2, 1]

위에서 가장 긴 바이토닉 수열을 갖기 위해
증가하는 수열의 길이 + 감소하는 수열의 길이가 최대가 되는 값을
증가 -> 감소 or 감소 -> 증가 하는 분기(sk)로 봐야한다.

위 케이스에서
바이토닉 수열 = [1,3,5,7,9,8,6,5,2]이며

숫자 9(index = 7) 에서 증가하는 수열-> 감소하는 수열로 변화할 때 가장 긴 바이토닉 수열을 갖는다.
즉, 9에서 가장 긴 바이토닉 수열을 가지므로 sk = 9가 된다.

증가하는 수열 = [1,3,5,7,9]
감소하는 수열 = [9,8,6,5,2]

증가하는 수열 길이[7] = 6
감소하는 수열 길이[7] = 4

정답 >
증가하는 수열 길이[7] + 감소하는 수열 길이[7] -1 = 9
( 1을 빼는 이유 : 9까지의 길이, 9부터의 길이 9를 두 번 계산했으므로 길이 1을 빼준다.)

코드

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

# 감소하는 수열을 증가하는 수열과 한번에 찾기 위해 수열을 뒤집음 
reverseA = A[::-1] 

inc_dp = [1]*n # 증가 dp
dec_dp = [1]*n # 감소 dp

for i in range(n):
    for j in range(i):
        # 증가 수열 
        if A[i] > A[j]:
            inc_dp[i] = max(inc_dp[i], inc_dp[j]+1)
        
        # 감소 수열 
        if reverseA[i] > reverseA[j]:
            dec_dp[i] = max(dec_dp[i], dec_dp[j]+1)

# 뒤집은 수열 복구 
dec_dp = dec_dp[::-1]

# 증가하는 수열 , 감소하는 수열 최대값 찾기 
result = []
for i in range(n):
    result.append(dec_dp[i] + inc_dp[i]-1)

print(max(result))