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

문제링크

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

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

---

 

코드

from bisect import bisect_left
def lis(arr):
    if not arr:return 0
    dp = [arr[0]]
    for i in range(len(arr)):
        if dp[-1]<arr[i]:
            dp.append(arr[i])
        else:
            dp[bisect_left(dp,arr[i])] = arr[i]
    return len(dp)

n = int(input())
data = [*map(int,input().split())]
mx = -1
for i in range(n):
    mx = max(mx,lis(data[:i+1])+lis([-i for i in data[i:]])-1)
print(mx)

---

 

문제풀이

긴 증가하는 바이토닉 부분수열을 구해주기 위해서 하나의 수열을 두 개의 부분수열로 나누어 한 부분수열의 LIS길이와 다른 한 부분수열의 LDS길이를 구한 후 더해줬다. 가장 긴 증가하는 부분수열을 구해야 하기 때문에 수열을 N번 돌며 모든 경우의 수에 대해 확인하고 max값을 구해줬다.

lis함수는 가장 긴 증가하는 부분수열의 길이를 return하는 함수이다. LIS 길이를 구할때 lis함수를 사용하고 LDS 길이를 구할 때는 파라미터로 들어가는 부분수열에 모두 -를 곱해줘서 lis를 함수를 사용해 구해줬다.

LIS를 구할 때 이진탐색을 이용하여서 시간복잡도는 nlogn이므로, 두 부분수열로 나누는 모든 경우를 확인해도 O(N*NlogN)으로 시간초과가 나지 않는다.