백준 - 11045번(DP,LIS 응용)

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

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

가장 긴 바이 토닉 부분 수열 문제다.

가장 긴 증가하는 부분 수열에서 감소가 추가된 것이다.

따라서 가장 긴 증가하는 부분 수열, 즉 LIS를 찾아준 다음에 뒤에서부터 다시 LIS를 찾아준다.

이렇게 나온 두개의 inc 배열과 dec 배열을 합친 다음에 1을 빼준다.

왜 1을 빼주냐면 가장 큰 값 즉 증감이 변하는 부분의 값이 두 번 들어갔기 때문이다.

합쳐서 나온 리스트에서 가장 큰 값을 찾아주면 그게 정답이다.

import sys

n = int(sys.stdin.readline())

arr = list(map(int,sys.stdin.readline().split()))

inc_dp = [1 for _ in range(n+1)]
dec_dp = [1 for _ in range(n+1)]
inc_dp[0] = 1
dec_dp[0] = 1


for i in range(1,n):
    for j in range(i):
        if arr[j] < arr[i] and inc_dp[j]+1 > inc_dp[i]:
            inc_dp[i] = inc_dp[j]+1

for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
        if arr[j] < arr[i] and dec_dp[j]+1 > dec_dp[i]:
            dec_dp[i] = dec_dp[j]+1

for i in range(n):
    inc_dp[i] = inc_dp[i] + dec_dp[i] - 1

print(max(inc_dp))

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

11053번: 가장 긴 증가하는 부분 수열

이 문제를 두번 반복한다고 보면 된다.

LIS를 제대로 이해했다면 아주 쉬운 문제

2 * O(NlogN) 으로 해결 가능