[백준] 11054 가장 긴 바이토닉 부분 수열 python 풀이

문제

• 난이도: 골드4
• 알고리즘 분류: 다이나믹 프로그래밍
• 요약: 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력하기

 

풀이

가장 긴 바이토닉 수열을 갖기 위해 (증가하는 수열의 길이 + 감소하는 수열의 길이)가 최대가 되는 수열을 찾아야 한다. 이를 위해 dp 배열을 사용하여 dp[i]에 arr[i]를 마지막 원소로 가지는 부분 수열에서의 최대 길이를 저장한다.

 

예제로 주어진 수열을 살펴보면

수열	1 5 2 1 4 3 4 5 2 1
i번째 원소를 마지막으로 하는 증가하는 부분 수열의 최대 길이	1 2 2 1 3 3 4 5 2 1
i번째 원소를 마지막으로 하는 감소하는 부분 수열의 최대 길이	1 2 3 3 3 4 1 2 5 1
두 수열의 합	2 7 4 2 7 6 7 8 4 2

가장 긴 바이토닉 수열은 8번째 원소를 기준으로 갖는다.

• 1 5 2 1 4 3 4 5 (증가하는 부분 수열)
• 5 2 1 (감소하는 부분 수열)
• 1 5 2 1 4 3 4 5 2 1 (증가하는 부분 수열 + 감소하는 부분 수열)

1번째~8번째 원소로 이루어진 증가하는 부분 수열과 8번째~10번째 원소로 이루어진 감소하는 부분 수열에서, 8번째 원소가 두 부분 수열에 모두 포함된다. 따라서 총 길이 계산 시 중복을 제거한다.

 

코드

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

reverse_arr = arr[::-1]

increase_dp = [1] * n
decrease_dp = [1] * n

for i in range(n):
    for j in range(i):
        # 증가하는 수열
        if arr[i] > arr[j]:
            increase_dp[i] = max(increase_dp[i], increase_dp[j] + 1)

        # 감소하는 수열
        if reverse_arr[i] > reverse_arr[j]:
            decrease_dp[i] = max(decrease_dp[i], decrease_dp[j] + 1)

decrease_dp = decrease_dp[::-1]

res = []
for i in range(n):
    res.append(increase_dp[i] + decrease_dp[i] - 1)
print(max(res))