백준 / 11054 가장 긴 바이토닉 부분 수열 python3

www.acmicpc.net/problem/11054

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

예전에 푼 문제인데 재채점 되면서 틀렸다하여 다시 풀었다. 

바이토닉 수열이란 수열이 S1 < S2 < .. < Sk > S_k+1 > ... > Sn 을 만족하는 k가 존재하는 수열을 말한다. 

수열이 주어졌을 때, 부분 수열 중 가장 긴 바이토닉 수열의 길이를 구하면 된다.

 

수열의 길이가 1000개이므로 O(N^2) 정도로 풀어도 충분한 시간이다. 

수열의 n번째 원소를 arr[n] 이라 하고, dp[n]을 arr[n]을 부분 수열의 마지막 원소라 하였을 때, 가능한 증가 부분 수열의 최대 길이라고 하자. 그렇다면 다음을 만족한다.

 

dp[n] = max( dp[i], dp[j], ..., dp[k] ) +1, where arr[n] > arr[i], arr[j], ..., arr[k] and i, j, ..., k < n

 

즉, 1 5 2 1 4 3 4 5 2 1 이라는 수열에서 arr[1] = 5는 arr[0] = 1보다 크므로, dp[1] = max(dp[0])+1 이고, 

arr[4] = 4는 arr[0]=1, arr[2]=2, arr[3]=1 보다 크므로 dp[4] = max(dp[0], dp[2], dp[3]) +1 이다. 

 

이 과정을 0~n-1 번째 원소까지 진행하고, 역방향 수열에 대해서 동일하게 진행하여 같은 index를 가지는 dp 끼리 더 하면 된다. 

 

코드는 다음과 같다.

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

dp1 = [0 for i in range(n)] # 정방향
dp2 = [0 for i in range(n)] # 역방향

for i in range(n):
    flag = arr1[i]
    for j in range(i):
        if arr1[j] >= flag:
            continue
        dp1[i] = max(dp1[i],dp1[j])
    dp1[i] += 1

for i in range(n):
    flag = arr2[i]
    for j in range(i):
        if arr2[j] >= flag:
            continue
        dp2[i] = max(dp2[i], dp2[j])
    dp2[i] += 1

dp2 = dp2[::-1]

result = 0
for i in range(n):
    result = max(result, dp1[i]+dp2[i])
    
print(result - 1) # flag 중복