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

백준 11054 - 가장 긴 바이토닉 부분 수열

문제

코드

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
inc = [0] * n
dec = [0] * n
b = [0] * n

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

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

for i in range(n):
    b[i] = inc[i] + dec[i]

print(max(b) - 1)

해설

해당 문제는 앞서 푼 LIS(Longest Increasing Subsequence)의 응용문제이다.

1. 입력: arr = list(map(int, input().split()))

2. DP이용
   바이토닉 수열은 증가하거나, 감소하거나, 증가하다 감소하는 수열이다.
   증가하다가 감소하는 수열이 증가하거나 감소하는 경우보다 항상 크므로 증가하다 감소하는 경우의 최댓값을 구해주면 된다.
   한 기준점에서 증가하는 최대수와 감소하는 최대수를 더하여 1을 빼주면 원하는 값이 나온다.
   증가하는 부분은 LIS 풀때와 마찬기지로 기준점 이전의 수에서의 최대길이중 가장 큰수에서 1을 더하여 구하였고
   감소하는 부분은 역순으로 검사하여 구하였다.

3. 값을 구하기 위해 b[i] = inc[i] + dec[i]를 해주었다.

4. 출력: print(max(b) - 1)