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

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

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

1. 알고리즘 유형 : DP 

증가하는 수열, 감소하는 수열 요런 유형은 DP 로 많이 접했어서 DP 라고 떠올렸다. 

정확하게는 DP 를 이용한 LIS (Longest Increasing Subsequence, 최장 증가 부분 수열)과 LDS (최장 감소 부분 수열) 을 활용하여 풀 수 있다. (상당히 문제가 naive하게 힌트를 주고 있다)

2. 풀이 

예전에 문제를 접한 적이 있어서 금방 떠올랐다. i번째 원소를 기준으로 증가하는 수열, 감소하는 수열 을 구한다음에 합치면 문제에서 원하는  S1< S2< ... Sk-1< Sk > Sk+1 > ... SN-1 > SN 를 만족하는 수열을 구할 수 있게 된다. 

증가하는 부분 수열과 감소하는 부분 수열을 각각 dp_up, dp_down 1차원 배열에 저장했다. 

여기서 dp_up[i] , dp_down[i] 의 의미는, i번째 원소를 포함했을 때 구할 수 있는 가장 긴 수열의 길이를 의미한다. 

문제에서의 예제로 풀어보면 다음과 같다. 

data = [1, 5, 2, 1, 4, 3, 4, 5, 2, 1]

 

i ) 증가하는 부분 수열의 경우 주어진 데이터 리스트를 왼쪽에서 오른쪽으로 선형탐색하여 구한다. 

dp_up[0]	dp_up[1]	dp_up[2]	dp_up[3]	dp_up[4]	dp_up[5]	dp_up[6]	dp_up[7]	dp_up[8]	dp_up[9]
{1}	{1, 5}	{1, 2}	{1}	{1,2,4}	{1, 2, 3}	{1, 2, 3, 4}	{1,2,3,4,5}	{1, 2}	{1}

ii ) 감소하는 부분 수열의 경우 주어진 데이터 리스트를 역방향 (오른쪽에서 왼쪽으로) 순회해서 구하면 된다. 즉, 오른쪽에서 왼쪽으로 진행하는 증가하는 부분 수열이라고 생각할 수 있다. 

dp_down[9]	dp_down[8]	dp_down[7]	dp_down[6]	dp_down[5]	dp_down[4]	dp_down[3]	dp_down[2]	dp_down[1]	dp_down[0]
{1}	{1, 2}	{1, 2, 5}	{1, 2, 4}	{1, 2, 3}	{1, 2, 3, 4}	{1}	{1, 2}	{1,2,3,4,5}	{1}

for i in range(N-1, -1, -1):
    for j in range(N-1, i, -1):
        if data[i] > data[j]:
            dp_down[i] = max(dp_down[i], dp_down[j]+1)

iii ) dp_up과 dp_down 의 결과를 합친다. 

마지막으로 구해놓은 dp_up 과 dp_down 을 합치는 부분에서 -1 을하는 이유는 

{1, 2, 3}, {3, 2, 1} 과 같은 예시에서 3이라는 원소가 겹치는데 한번만 카운트 해주어야 하기 때문이다. 

dp = [0] * N
for i in range(N):
    dp[i] = dp_up[i] + dp_down[i] -1 # 중복 원소 삭제

 

3. 전체 코드 

N = int(input())
data = list(map(int, input().split()))
# 1. 증가하는 부분 수열 구하기
dp_up = [1] * N

for i in range(N):
    for j in range(i):
        if data[i] > data[j]:
            dp_up[i] = max(dp_up[i], dp_up[j] + 1)
# 2. 감소하는 부분 수열 구하기
dp_down = [1] * (N+1)

for i in range(N-1, -1, -1):
    for j in range(N-1, i, -1):
        if data[i] > data[j]:
            dp_down[i] = max(dp_down[i], dp_down[j]+1)

# 3. 합쳐서 최대 길이 구하기
dp = [0] * N
for i in range(N):
    dp[i] = dp_up[i] + dp_down[i] -1 # 중복 원소 삭제
    
print(max(dp))