🐹 가장 긴 바이토닉 부분 수열

1. 문제 링크

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

2. 코드

Python3 31120KB 272ms

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

in_dp = [0 for _ in range(N)]
de_dp = [0 for _ in range(N)]

# 증가 순열 dp
for i in range(N):
    for j in range(i):
        if A[i] > A[j]:
            in_dp[i] = max(in_dp[i], in_dp[j] + 1)

# 감소 순열 dp
for i in range(N-1, -1, -1):
    for j in range(N-1, i, -1):
        if A[i] > A[j]:
            de_dp[i] = max(de_dp[i], de_dp[j] + 1)

print(max([in_dp[i] + de_dp[i] for i in range(N)])+1)

3. 해설

k번째 수를 기준으로 왼쪽은 증가하는 순열, 오른쪽은 감소하는 순열로 나누어 (증가하는 순열 + 감소하는 순열)의 최댓값을 구하면 된다.

증가 순열 dp와 감소 순열 dp 배열을 0으로 초기화한 후 각각 구해준다.

증가하는 순열에서 dp[i]는 i번째를 기준으로 앞의 증가하는 순열의 최대 크기이다. 감소하는 순열에서 dp[i]는 i번째를 기준으로 뒤의 감소하는 순열의 최대 크기이다.

합의 최댓값을 구하고 난 후 k번째 숫자까지 1을 더해준다.