[BOJ][Python]11054 풀이

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

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

def f(n, arr):
    dp = [1 for _ in range(n)]
    for i in range(n):
        for j in range(i):
            if arr[i] > arr[j]: # 현재 원소가 처음부터 비교해오는 원소보다 크면
                if dp[i] < dp[j]+1:
                    dp[i] = dp[j]+1
    return dp

n = int(input())
a = list(map(int, input().split()))
dp = f(n, a)
dp1 = f(n, a[::-1])[::-1]
ans = [dp[i]+dp1[i]-1 for i in range(n)]
print(max(ans))

최장 수열 문제입니다. 예전에 최장 공통 문자열과 비슷하면서 살짝 다른 유형이라고 생각하시면 될 것 같아요. 여기서 테이블이 가지는 의미는 '해당 원소를 마지막 원소로 사용하는 수열의 길이'입니다. 또, 바이토닉이라 증가만 하거나, 감소만 하거나, 증가하다가 감소하거나의 3가지 경우가 다 가능하기 때문에 증가하는 최장 수열 테이블과 감소하는 최장수열 테이블을 따로 구해서 원소끼리 더해서 최댓값을 구하면 3가지 경우에 모두 대응되는 최장 수열을 구할 수 있겠죠.

 

풀이는 보통 동적 계획법을 사용하지만 시간복잡도를 줄이기 위해 이분탐색을 사용하기도 합니다. 해당 문제는 이분탐색을 사용하지 않아도 넉넉하게 통과가 됩니다만, 다음에 입력조건이 훨씬 큰 문제를 만나면 그 때는 이분탐색을 꼭 사용해야겠죠. 이분탐색을 사용하는 풀이는 또 그 때 알아보면 좋을 것 같습니다.

 

추가// LIS 풀이 포스팅을 올리고나니까 그냥 놔두기 뭐해서 이진 탐색을 사용한 코드도 한 번 올려봅니다.

def bs(subs, cur_num):
    start = 0
    end = len(subs)
    while start < end:
        mid = (start + end)//2
        if cur_num > subs[mid]:
            start = mid+1
        else:
            end = mid
    return end

def lis(arr):
    dp = [1 for _ in range(n)]
    subs = [arr[0]]
    for i in range(1, n):
        if arr[i] > subs[-1]:
            subs.append(arr[i])
        else:
            bs_idx = bs(subs, arr[i])
            subs[bs_idx] = arr[i]
        dp[i] = len(subs)
    return dp

n = int(input())
a = list(map(int, input().split()))
asc = lis(a)
des = lis(a[::-1])[::-1]
ans = [asc[i]+des[i]-1 for i in range(n)]
print(max(ans))