백준 11054 가장 긴 바이토닉 부분 수열 (파이썬)
접근방식
- 11053 가장 긴 증가하는 부분 수열이 순방향으로 체크를 한다면 이 문제는 역방향으로도 체크를 해주는 방식이다.
- 11053 가장 긴 증가하는 부분 수열 문제 해설은 아래 링크에서 확인해볼 수 있다.
https://ataraxiady.github.io/dev/2021/03/30/dev-boj-1_11053/
파이썬 코드
import sys
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
dp1 = [0 for i in range(n)]
dp2 = [0 for i in range(n)]
total = [0 for i in range(n)]
# 순방향
for i in range(n):
for j in range(i):
# index 0부터 i-1까지 arr와 dp값을 비교한다
# arr[i]가 arr[j]보다 큰데 dp[i]는 작을 경우 dp[i] 값을 dp[j]로 바꿔준다.
# (값은 큰데 카운트 값은 작은 경우)
if arr[i] > arr[j] and dp1[i] < dp1[j]:
dp1[i] = dp1[j]
# 조건없이 +1을 한다.
dp1[i] = dp1[i] + 1
# 역방향
for i in range(n-1,-1,-1):
for j in range(n-1,i,-1):
if arr[i] > arr[j] and dp2[i] < dp2[j]:
dp2[i] = dp2[j]
dp2[i] = dp2[i] + 1
for i in range(n):
total[i] = dp1[i] + dp2[i] - 1
print(max(total))
