해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 11054 가장 긴 바이토닉 부분 수열 - dp

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

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.
예를 들어, {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} 은 바이토닉 수열이 아니다.
수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

풀이

1. dp로 풀 수 있는 문제입니다.

https://zidarn87.tistory.com/285 에 설명되어 있는 11053번 문제와 유사한 문제입니다.

2. 증가하는 수열을 위해 i = 0부터 bottom-up 식으로 현재 위치(i)가 이전에 있는 원소(j)가 큰지를 확인하여, 크다면, 그 위치의 dp값에 1을 더해주면 됩니다.
3. 감소하는 수열을 위해 i = n-1 부터 top-down식으로 현재 위치(i)가 이전에 있는 원소(j)가 큰지를 확인하여, 크다면, 그 위치의 dp값에 1을 더해주면 됩니다.

4. 인덱스별로 증가하는 수열 길이 + 감소하는 수열 길이의 합이 가장 큰 지점이 바이토닉 수열의 Sk 원소가 됩니다.

전체 코드

n = int(input())
arr = list(map(int, input().split()))
dpup   = [0 for i in range(n)]
dpdown = [0 for i in range(n)]
dpmix  = [0 for i in range(n)]

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

for i in range(n - 1, -1, -1):
    for j in range(n - 1, i, -1):
        if arr[i] > arr[j] and dpdown[i] < dpdown[j]:
            dpdown[i] = dpdown[j]
    dpdown[i] += 1
#print(dpdown)
for i in range(n):
    dpmix[i] = dpup[i] + dpdown[i] - 1
#print(dpmix)
print(max(dpmix))