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

17 Jun 2023 in Study on Algorithm

백준11054 가장 긴 바이토닉 부분 수열 링크

문제

예제 입력

---

코드

import sys
input = sys.stdin.readline

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

dp1 = [0] * N
for i in range(N):
    for j in range(i):
        if arr[j] < arr[i] and dp1[i] < dp1[j]:
            dp1[i] = dp1[j]
    dp1[i] += 1

dp2 = [0] * N
for i in range(N-1, -1, -1):
    for j in range(N-1, i, -1):
        if arr[j] < arr[i] and dp2[i] < dp2[j]:
            dp2[i] = dp2[j]
    dp2[i] += 1

ans = [dp1[i]+dp2[i]-1 for i in range(N)]
print(max(ans))

설명

파이썬을 통해서 사용자로부터 입력받아 dp알고리즘을 사용하여 가장 긴 바이토닉 부분 수열를 구현했습니다.

---

결과