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

import sys
input = sys.stdin.readline

def BOJ11054() :
  n = int(input())
  l = list(map(int, input().split()))

  dp_up = [1 for _ in range(n)]
  dp_down = [1 for _ in range(n)]

  for i in range(n) :
    for j in range(i) :
      if l[i] > l[j] :
        dp_up[i] = max(dp_up[i], dp_up[j]+1)

  for i in range(n-1, -1, -1):
    for j in range(n-1, i-1, -1):
      if l[i] > l[j]:
        dp_down[i] = max(dp_down[i], dp_down[j]+1)

  dp = []
  for up, down in zip(dp_up, dp_down) :
    dp.append(up + down - 1)
  
  print(max(dp))
  
BOJ11054()

 

접근 방법 :

1. 배열 두개를 생성해 주었다. 

1. 시작점에서부터 점점 커져가는 배열
2. 끝점에서부터 점점 작아지는 배열

2. 두개의 배열을 가지고 각 점에서 가지는 값들을 더해준다. 그리고 -1을 해주면 바이토닉 부분 수열의 길이를 알수있다.

3. dp 배열중 최댓값을 출력해주면 끝

 

 

 

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

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