[BOJ] 11054. 가장 긴 바이토닉 부분 수열

Python3,DP

문제

입출력

입출력 예시

주요 포인트

가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열을 혼합한 문제이다.

    주어진 수열:  1, 5, 2, 1, 4, 3, 4, 5, 2, 1

증가하는 수열 길이: 1, 2, 2, 1, 3, 3, 4, 5, 2, 1

감소하는 수열 길이: 1, 5, 2, 1, 4, 3, 3, 3, 2, 1

증가하는 수열 1, 2, 3, 4, 5
감소하는 수열 5, 2, 1
이 된다. 이때 Sk 값은 5이고, 증가하는 수열과 감소하는 수열 둘 다 포함돼 2번 계산된다.
따라서 마지막에 -1을 해줘야 한다.

최종 코드

n = int(input())
a = list(map(int, input().split()))
re_a = a[::-1]

up = [1 for i in range(n)]
down = [1 for i in range(n)]

dp = [0 for i in range(n)]

for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            up[i] = max(up[i], up[j]+1)
        if re_a[i] > re_a[j]:
            down[i] = max(down[i], down[j]+1)

for i in range(n):
    dp[i] = up[i] + down[n-i-1] - 1
    
print(max(dp))

주어진 수열 a와 수열 a를 거꾸로 뒤집은 re_a를 선언한다.
수열 up에는 증가하는 수열 길이가, 수열 down에는 감소하는 수열 길이가 들어갈 것이다.
dp에는 바이토닉 수열 길이(증가하는 수열 길이 + 감소하는 수열 길이 - 1)가 들어간다.

이전 문제와 같이 수열[i]와 수열[j]의 값을 비교해서 이전값에 + 1과 현재값 중 큰 수를 배열에 넣는다.

수열 dp 중 가장 큰 값을 출력하면 바이토닉 수열의 길이를 구할 수 있다.

피드백

증가하는 부분 수열의 길이와 감소하는 부분 수열의 길이를 합하는 것이 이 문제의 핵심 포인트였다. 또한 입력 받은 수열을 그대로 쓰는 게 아니라, 기존 수열을 reverse 시켜 사용하는 것도 배울 수 있는 문제였다.