백준 11054: 가장 긴 바이토닉 부분 수열 python

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

---

문제접근

수열이 주어졌을 때 가장 긴 바이토닉 수열의 길이를 출력하는 문제.

바이토닉 수열(Bitonic Sequence)은 다음 두 조건을 만족하는 수열이야:

어느 한 지점을 기준으로 왼쪽은 strictly 증가하고, 오른쪽은 strictly 감소하는 수열

즉,증가하다가 어느 시점을 기준으로감소하는 형태를 가진 수열.

[1, 2, 3, 4, 5] → 끝까지 증가만 함 -> 바이토닉 X
[5, 4, 3, 2, 1] → 끝까지 감소만 함 -> 바이토닉 X
[1, 3, 2, 4] → 증가하다 감소했다 다시 증가함 → 바이토닉 X

---

수열 A가 주어졌을 때,

dp_increase[i]: i를 끝으로 하는 가장 긴 증가 부분 수열의 길이

dp_decrease[i]: i를 시작으로 하는 가장 긴 감소 부분 수열의 길이

각 인덱스 i를 기준으로:

바이토닉 수열의 길이 = dp_increase[i] + dp_decrease[i] - 1

(-1 하는 이유는 i가 중복되기 때문)

---

해답 및 풀이

# 수열의 길이 입력
n = int(input())

# 수열 입력
A = list(map(int, input().split()))

# 각 위치를 끝으로 하는 '최장 증가 부분 수열'의 길이를 저장
dp_increase = [1] * n

# 각 위치를 시작으로 하는 '최장 감소 부분 수열'의 길이를 저장
dp_decrease = [1] * n

# dp_increase[i] 계산: A[i]를 끝으로 하는 증가 수열
for i in range(n):
    for j in range(i):  # i보다 앞에 있는 원소들 확인
        if A[j] < A[i]:  # 증가 조건
            dp_increase[i] = max(dp_increase[i], dp_increase[j] + 1)

# dp_decrease[i] 계산: A[i]를 시작으로 하는 감소 수열
for i in range(n - 1, -1, -1):  # 뒤에서부터 시작
    for j in range(n - 1, i, -1):  # i보다 뒤에 있는 원소들 확인
        if A[j] < A[i]:  # 감소 조건
            dp_decrease[i] = max(dp_decrease[i], dp_decrease[j] + 1)

# 바이토닉 수열의 최대 길이 구하기
# 각 위치 i를 기준으로, 증가 + 감소 - 1 (i가 중복되므로 -1)
max_length = 0
for i in range(n):
    length = dp_increase[i] + dp_decrease[i] - 1
    max_length = max(max_length, length)

# 결과 출력
print(max_length)