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

---

문제설명

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

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

사고과정

• 문제에서 설명하는 바이토닉 부분 설명 정의에 의해서 주어진 수열 안에서 증,감하고 다시 증가하는 부분을 캐치해서 수열의 길이를 구해야 하는 건지 복잡했다.. 결국 풀지 못하고 구글링을 염탐했다..
• 풀이를 보니 주어진 수열을 가장 긴 증가하는 부분 수열 길이, 가장 긴 감소하는 부분 수열 길이 별로 DP테이블을 따로 구한 후, 이 두 DP 테이블 간의 동일한 인덱스에 있는 두 수의 합이 바로 바이토닉 수열 길이를 의미한다..! 이 때, 두 수의 합에서 -1을 해주어야 하는데, 왜냐하면 중간에 있는 수를 2번 더해줬기 때문이다. 예를 들어, 1, 2, 3, 4, 3, 1 이라는 바이토닉 수열이 있다고 해보자. 그러면 증가하는 부분 수열은 1, 2, 3, 4 를 나타낼 것이다. 반면 감소하는 부분 수열은 4, 3, 1 을 나타낸다. 각 길이는 4, 3 이다. 이 두 수를 합하면 7이지만 방금 정의한 바이토닉 수열은 길이가 6이였다. 즉, 중간에 공통으로 공유하고 있는 원소 '4' 한 개가 있기 때문에 -1을 해주어야 한다.
• 알고리즘 개념을 사용해야 한다라는 관점에서 풀이를 해야할 필요가 있는 듯하다. 그리고 주어진 수열 1개로만 생각하지 말고 이를 분리해서 풀어볼 수 있지 않을까 하는 사고의 확장도 아직 부족한 듯 싶다.

풀이(스스로 못 푼 풀이)

n = int(input())
array = list(map(int, input().split()))
lis_dp = [1] * n
lds_dp = [1] * n
for i in range(1, n):
    for j in range(0, i):
        if array[j] < array[i]:
            lis_dp[i] = max(lis_dp[i], lis_dp[j] + 1)

array.reverse()
for i in range(1, n):
    for j in range(0, i):
        if array[j] < array[i]:
            lds_dp[i] = max(lds_dp[i], lds_dp[j] + 1)
lds_dp = list(reversed(lds_dp))

# 바이토닉 수열 길이가 최대인 것 구하기
max_sum = 0
for i in range(n):
    max_sum = max(max_sum, lis_dp[i]+lds_dp[i] - 1)

print(max_sum)