백준 11054번 파이썬 문제풀이(DP - 가장 긴 바이토닉 부분 수열)

---

사실 이 문제는 앞선 가장 긴 증가하는 혹은 감소하는 부분수열문제에서 약간 꼬아낸 문제이다. 우선 이 문제를 해결하기 위해서는 2가지를 생각할 수 있어야 한다.

1. 입력받은 수열의 각 원소마다 '앞에서' 몇번째로 증가하는 부분 수열 인지 확인(이전의 가장 긴 부분수열을 구하는 알고리즘과 동일)

2. 입력받은 수열의 각 원소마다 '뒤에서' 몇번째로 증가하는 부분 수열인지 확인(입력받은 수열을 거꾸로 뒤집고 구해도 됨)

 

-> 예를 들어 위 예제 입력에서 1 5 2 1 4 3 4 5 2 1 이있다고 치자. 그렇다면 1 2 3 4 5 는 증가하는 수열이며 5 2 1 은 감소하는 수열이다. 즉 8번째  '5' 를 기준으로 앞에서는 5번째 증가 부분수열이며 뒤에서 3번째로 증가하는 부분 수열이다.  총 배열 길이는 5가 2번들어가있으므로 -1 을 해준 7이 된다.

또 위의 예제에서 2번째 5를 기준으로 1 5 는 증가하는 수열이며 5 2 1 은 감소하는 수열이다.  바이토닉 수열 길이는 3이 된다.

혹은 5번째 4 를 기준으로 1 2 4 는 증가하는 수열 4 2 1 은 감소하는 수열이 된다. 바이토닉 수열 길이는 5가 된다.

(이문제의 핵심은  LIS를 양방향에서 한다는 것이다!!!!!)

 

즉 이런식으로 입력한 배열의 원소 하나를 뽑아서 앞에서 몇번째로 증가하는 부분 수열인지 그리고 뒤에서는 몇번째로 증가하는 부분수열인지를 다 구해서 가장 큰값을 구하면 되는 문제이다.

import sys

input = sys.stdin.readline

N = int(input())
input_array = list(map(int, input().split()))
dp_increase = [1] * N  # 증가하는 부분수열

# 뒤에서부터 증가하는 부분수열을 구하기위해 배열을 반대방향으로 돌린다.
reversed_input_array = list(reversed(input_array))
dp_decrease = [1] * N  # 뒤에서 증가하는 부분수열(정방향으로는 감소하는 부분수열)

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

result = []
for i in range(N):
    result.append(dp_increase[i] + dp_decrease[N - i - 1] - 1)

print(max(result))

위와 같이 배열을 반대 방향으로 돌려서 한번의 반복문안에 구할 생각을 하지 못한다면 따로따로 구해도 약간의 시간적 복잡도 손해는 있지만 크게 차이나는 시간복잡도는 아니기에 다음과 같이 코드를 짜는 것을 권한다.

 

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

ans = 0
dp_1 = [1] * N
dp_2 = [1] * N
for i in range(N):
    for j in range(i):
        if arr[i] > arr[j]:
            dp_1[i] = max(dp_1[i], dp_1[j] + 1)

for i in range(N)[::-1]:
    for j in range(i + 1, N)[::-1]:
        if arr[i] > arr[j]:
            dp_2[i] = max(dp_2[i], dp_2[j] + 1)

ans = 0
for i in range(N):
    ans = max(ans, dp_1[i] + dp_2[i])
print(ans - 1)