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

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

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

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

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

 

풀이

[BOJ] 11053 / 가장 긴 증가하는 부분 수열 과 [BOJ] 11722 / 가장 긴 감소하는 부분 수열 을 동시에 찾는 문제이다.

 

비교 기준 값의 index 를 기준으로, 왼쪽으로는 가장 긴 증가 부분 수열의 길이를 오른쪽으로는 가장 긴 감소 부분 수열 길이를 찾는 문제이다.

 

 

index의 오른편의 가장 긴 증가 부분 수열 길이는 이전의 문제 풀이 방법과 같이 풀었다.

index의 왼편의 가장 긴 감소 부분 수열은, index 의 끝에서 현재 index 까지 반대 방향의 가장 긴 부분 수열의 길이를 구하여 풀었다.

 

N = int(input())

nums = list(map(int, input().split()))

upDp = [1] * N
downDp = [1] * N

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

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

result = [0] * N
for i in range(N):
    result[i] = upDp[i] + downDp[i]

print(max(result)-1)

 

※ 거꾸로 index 연산을 할 때 주의하자.