[백준] 11054번 - 가장 긴 바이토닉 부분 수열 (DP) - 결과 포함

www.acmicpc.net/problem/11054

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

이전에 풀었던 11053번 가장 긴 증가하는 부분 수열 문제의 응용버전이다.

바이토닉 수열은 증가하는 부분과 감소하는 부분이 동시에 존재한다.

 

증가하는 수열과 감소하는 수열을 둘로 나누어서 메모하는 아이디어는 생각했지만

실제로 어떻게 구현할 지를 생각하지 못했다.

 

다른 분의 글을 참고해서 이해했다.

예를 들어 본다.

 

1 2 3 2 1

이라는 바이토닉  수열이 있다.

증가하는 부분은 1 2 3

감소하는 부분은 3 2 1 이다.

 

이전에 증가하는 부분 수열을 구할 때와 같은 방법을 사용해서 감소하는 부분도 구한다.

끝에서부터 반복문을 반대로 돌면서 증가하는 수열을 구하면

 

증가하는 부분 수열과 감소하는 부분 수열의 최대 길이를 구할 수 있다.

이 증가하는 부분 수열과 감소하는 부분 수열의 길이를 각각 더하면

바이토닉 부분 수열의 각 인덱스에서의 최대 길이를 구할 수 있다.

 

하지만 최대 길이에서 1을 빼주어야 한다.

위에서 각각을 더하면

2 4 6 4 2 가 나올 것이다.

이 때 6은 3에서 자기 자신이 중복된 것을 알 수 있다.

수열을 보아도 전체 길이가 5인 것을 확인 할 수 있다.

 

[소스 코드]

n = int(input())

data = list(map(int, input().split()))
arr = [1] * (n + 1)
di = [1] * (n + 1)
dd = [1] * (n + 1)

for i in range(1, n + 1):
    arr[i] = data[i - 1]

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

for i in range(n, 0, -1):
    for j in range(n, i, -1):
        if arr[i] > arr[j]:
            dd[i] = max(dd[j] + 1, dd[i])

d = [1] * (n + 1)
for i in range(1, n + 1):
    d.append(di[i] + dd[i])

print(max(d) - 1)