[백준] 11054번 가장 긴 바이토닉 부분 수열(feat. 다이나믹 프로그래밍, LIS, LDS)

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

• 첫 번째 단계(문제 요약 및 조건 파악하기)

문제에서 말하는 바이토닉 수열에 대해서 간단하게 정리하면,
어떤 특정 수 X를 기준으로 왼쪽은 X보다 작은 LIS, 오른쪽은 X보다 작은 LDS 인 수열이다.

예를 들어, {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} 은 바이토닉 수열이 아니다.

입력 조건으로는,
수열의 크기 N은 1 <= N <= 1000
수열을 이루는 수 Ai는 1 <= Ai <= 1,000 이다.

 

• 두 번째 단계(문제 핵심 파악하기)

간단하게 생각해보면,
특정수를 기준으로 왼쪽은 LIS를 구하고, dp_left에 저장하고,
특정수를 기준으로 오른쪽은 LDS를 구해서,dp_right에 저장해놓은 후,

인덱스에 맞춰서 dp_lieft[i] + dp[right[i]가 가장 큰 값을 저장하고,
저장한 값에다가 공통으로 가지고 있는 특정 수는 2번 중복되었으므로 -1을 해주면 우리가 구하고자하는 가장 긴 바이토닉 부분 수열이 될 것이다.

근데 잘 생각해 볼 것이 있다.
만약에 특정 수를 기준으로 왼쪽은 LIS, 오른쪽은 LDS 구하는 과정을 하게 된다면,
O^3의 시간이 소요될 것으로 예상된다. 그러면, 입력의 최댓값인 1000의 ^3을 고려했을 때, 시간초과가 날 것으로 예상된다.

그러면, 조금 다른 방법을 생각해 봐야한다.

더 간단한 방법이 있다.

처음 부터 특정 수를 기준으로 LIS, LDS를 각각 구하지 말고,

주어진 배열 arr[]의 LIS와 LDS를 한번씩 구하고,
이 두 배열의 같은 인덱스의 값 끼리 더한 값이 가장 큰 값에서 -1을 해주면 우리가 구하고자 하는 바이토닉 부분수열의 가장 긴 길이가 나온다.

-1을 해주는 이유는,
예를 들어 [1, 2, 3, 2, 1]의 수열이 있다고 가정하면,
LIS[2] + LDS[2]를 하게 되면, 인덱스 2에 해당하는 부분이 두번 더해지므로 -1을 해준 것이다.

'''
수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN 을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.
{10, 20, 30, 25, 20}이 있으면, 30을 기준으로 잡았을 때 바이토닉 수열이 성립된다.
그렇다면, 30을 기준으로 잡을 수 있었던 이유는 무엇일까? 30 왼쪽은 30보다 작으면서 멀어질수록 더 작고, 30오른쪽도 30보다 작으면서 멀어질수록 더 작다.
그렇다면 어떤 수열이 주어졌을 때, 그 수열의 부분 수열 중, 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 방법을 생각해보자.

i)
주어진 배열 arr[]에 대해서
원본 배열에서 LIS 를 구하고,
arr[]을 뒤집어서 LIS를 구하고, 그것을 다시 뒤집으면 arr에 대한 LDS를 구한 값이 된다.
그러면 LIS 배열과 LDS 배열의 같은 인덱스 부분을 더한 값이 가장 큰 값에다가 공통으로 겹치는 인덱스 부분을 고려하여 -1만 해주면 우리가 구하고자하는
가장 긴 바이토닉 부분 수열을 구할 수 있다.
'''

코드를 작성해보자.

 

코드 작성

import copy
import sys

n = int(sys.stdin.readline().rstrip())
arr = list(map(int, sys.stdin.readline().rstrip().split()))
candidate_list = [0 for i in range(n)]

dp_left = [0 for i in range(n)]
dp_right = [0 for i in range(n)]

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

reverse_arr = copy.deepcopy(arr)
reverse_arr.reverse()   # arr을 뒤집어서 LIS를 구하기 위함

for i in range(n):
    for j in range(i):
        if reverse_arr[i] > reverse_arr[j] and dp_right[i] < dp_right[j]:
            dp_right[i] = dp_right[j]
    dp_right[i] = dp_right[i] + 1

dp_right.reverse()  # arr을 뒤집어서 LIS를 구한 것을 다시 뒤집으면 arr에 대한 LDS(단, 직접 수열을 구하려면, 앞에서부터 큰 값의 인덱스을 찾고, 중복되는 값은 가장 마지막 인덱스를 찾아서 원본 배열과 매칭시켜주면 된다.
result = 0
for i in range(n):
    bitonic =  dp_left[i] + dp_right[i]
    if bitonic > result:
        result = bitonic
result = result - 1 # 공통으로 겹치는 인덱스를 한번 빼줌

print(result)