<백준 문제풀이: 11054번> 파이썬 - 가장 긴 바이토닉 부분 수열

이전의 [백준 11053번]과 매우 비슷한 문제이다. 다른 점은 앞으로 뒤로 합해서 가장 긴 수열을 찾는 것이었다.

import sys

N = int(sys.stdin.readline())
num_list = list(map(int, sys.stdin.readline().split()))
dp_front = [0 for x in range(N)]
dp_back = [0 for x in range(N)]

for i in range(N):
    for j in range(i):
        if num_list[i] > num_list[j] and dp_front[i] < dp_front[j]:
            dp_front[i] = dp_front[j]
    dp_front[i] += 1

for i in reversed(range(N)):
    for j in range(i+1, N):
        if num_list[i] > num_list[j] and dp_back[i] < dp_back[j]:
            dp_back[i] = dp_back[j]
    dp_back[i] += 1

sum_list = [sum(x) for x in zip(dp_front, dp_back)]
print(max(sum_list)-1)

이를 해내기 위해 앞에서 세주는 것은 물론 뒤로도 숫자를 세준 후, 이를 각각 배열에 저장시킨다. 이후, zip함수를 이용하여 같은 index 들끼리 묶고, 각 요소의 합을 구한다. 여기서 가장 큰 합을 가진 요소가 문제의 해답이 되는데, 여기서 한 숫자를 두번 세주는 경우가 발생하므로, 1을 빼준 값을 출력하몀ㄴ 바이토닉 부분 수열의 가장 긴 길이를 구할 수 있다.