[백준] 11054번 - 가장 긴 바이토닉 부분 수열 (파이썬) 문제 및 풀이

문제) 백준 - 동적 계획법 (Dynamic programming) - 가장 긴 바이토닉 부분 수열

-> www.acmicpc.net/problem/11054

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

 

(백준 - 11053번)가장 긴 증가하는 부분 수열 문제와 (백준 - 11722번) 가장 긴 감소하는 부분 수열 문제를 합치면 풀 수 있다.

가장 긴 증가하는 부분 수열의 아이디어를 채택해 우리는 1~n까지 탐색( i )하면서 그 이전까지 i번째 숫자보다 작으면서도 가장 긴 증가하는 부분 수열의 길이를 저장한다.

가장 긴 증가하는 부분 수열 다음에 수열이 감소해야되므로, 뒤에서부터 탐색하면서 가장 긴 감소하는 부분 수열을 찾는다. 

1~n까지 증가 부분 수열과 감소 부분 수열의 길이를 합쳐 최대를 구한다.

 

 

소스 코드)

import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))

increase_length = [0] * n
decrease_length = [0] * n
res = [0] * n

#가장 긴 증가하는 부분 수열
for i in range(n):
    for j in range(i):

        if num[j] < num[i] and increase_length[j] > increase_length[i]:
            increase_length[i] = increase_length[j]

    increase_length[i] += 1


#가장 긴 감소하는 부분 수열
for i in range(n - 1, -1, -1):
    for j in range(n - 1, i, -1):

        if num[j] < num[i] and decrease_length[j] > decrease_length[i]:
            decrease_length[i] = decrease_length[j]

    decrease_length[i] += 1
    

for i in range(n):
    res[i] = increase_length[i] + decrease_length[i]

print(max(res) - 1)

 

 

참고)

2021.03.02 - [Algorithm_note/틀린 문제] - [백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬)

[백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬)

2021.03.09 - [백준_BOJ] - [백준] 11722번 - 가장 긴 감소하는 부분 수열

[백준] 11722번 - 가장 긴 감소하는 부분 수열