[BOJ] 11054번: 가장 긴 증가하는 바이토닉 부분수열

https://www.acmicpc.net/

 

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

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

 

 

문제 풀이

백준 11053번 문제를 풀고 난 후 바로 도전한 문제여서 쉽게 해결 가능했다. 만약 안풀었다면 먼저 풀어보기!

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

11053번: 가장 긴 증가하는 부분 수열

다음 링크는 파이썬으로 해결한 풀이!

https://miraekwak.tistory.com/89

[BOJ] 11053번: 가장 긴 증가하는 부분수열 / 11054번: 가장 긴 증가하는 바이토닉 부분수열

 

문제는 간단했다. dp를 이용하여 배열의 왼쪽에서 시작, 오른쪽에서 시작 두가지 경우에 대해서 증가하는 수열 길이를 찾고 그 두가지 결과를 더해 길이가 제일 긴 것을 고르면 된다.

 

 

Python3

import sys
n = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))

dp_right = [0]*n
dp_left = [0]*n
for i in range(n):
    for j in range(i):
        if numbers[j] < numbers[i] and dp_right[j] > dp_right[i]:
            dp_right[i] = dp_right[j]
    dp_right[i] += 1
for i in range(n-1, -1, -1):
    for j in range(i, n):
        if numbers[j] < numbers[i] and dp_left[j] > dp_left[i]:
            dp_left[i] = dp_left[j]
    dp_left[i] += 1
for i in range(n):
    dp_left[i] += dp_right[i]
print(max(dp_left)-1)

left는 왼쪽에서 시작해 오른쪽으로 증가하는 수열의 최대길이를 찾는 배열이다.

right는 오른쪽에서 시작해 왼쪽으로 증가하는 수열의 최대길이를 찾는 배열이다.

여기서 중요한 점은 마지막 최대 길이 출력에서 1을 빼줘야 한다는 점! 바이토닉 배열의 최대길이가 나오게 되는 지점은 최대 값으로서 상승 하강의 지점이 된다. 따라서 이 지점이 두 배열 모두에서 카운트 되기 때문에 빼주는 것이 필요하다.