알고리즘 스터디 - 백준 11054번 : 가장 긴 바이토닉 부분 수열

문제 해석

수열 A에 대하여 그 수열의 부분 수열 중 가장 긴 바이토닉 부분 수열의 길이를 구하는 프로그램

어떤 알고리즘을 써야할까?

바이토닉 부분 수열의 특징

• 특정 수를 기준으로 좌우 방향으로 점점 작아지는 수를 말한다.

10
1 5 2 1 4 3 4 5 2 1

틀린 해석

1. 처음 시작하는 부분을 count[0] = 1로 선언
2. 5와 1을 비교해 커졌으니 count[1] = count[0] + 1 = 2
3. 5와 2를 비교해 작아졌는데 count[2] = count[1] + 1 = 3
4. 2와 1을 비교해 작아졌으니 count[3] = count[2] + 1 = 4
5. 1과 4를 비교했을 때 커진 경우가 앞에서 발견이 됐으므로 기존 시작점을 1로 갱신
   • count[4] = 1 + 1 = 2로 다시 선언
6. 4와 3을 비교했을 때 작아졌으므로 count[5] = count[4] + 1 = 3
7. 3과 4를 비교했을 때 다시 증가하므로 count[6] = 1 + 1 = 2
8. 위 과정을 반복해 count를 갱신하고 최종적으로 가장 큰 값을 출력

맞는 해석

가장 긴 부분 수열을 응용하여 앞뒤 2 방향으로 문제를 풀어나가면 된다.

기존 가장 긴 증가하는 부분 수열의 코드

dp = [1 for i in range(x)]

for i in range(x):
    for j in range(i):
        if arr[i] > arr[j]:
            dp[i] = max(dp[i], dp[j]+1)

• 이 방식은 1) 앞에서 뒤로 훓어나가는 것인데 이 방식을 응용해 2) 뒤에서 앞을 훓어나가는 방식도 구하면 된다.

알고리즘 코드

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))

dp_increase = [1 for _ in range(N)]
dp_decrease = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            dp_increase[i] = max(dp_increase[i], dp_increase[j] + 1)

for i in range(N-1, -1, -1):
    for k in range(N-1, i, -1):
        if A[i] > A[k]:
            dp_decrease[i] = max(dp_decrease[i], dp_decrease[k] + 1)

dp_total = [x+y-1 for x, y in zip(dp_increase, dp_decrease)]
print(max(dp_total))