[백준11054&파이썬] dp를 두번 이용하여 문제를 해결하자

# 문제

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

# 코드

import sys

n = int(sys.stdin.readline().strip())
arr = list(map(int,sys.stdin.readline().split()))

# print(arr)
# 왼쪽부터 증가하는 수열을 구한다.
dpL = [1] * n
for pivot in range(n) :
  for i in range(pivot) :
    if arr[i] < arr[pivot] :
      dpL[pivot] = max(dpL[pivot], dpL[i] + 1)
# print(dpL)

# 오른쪽부터 증가하는 수열을 구한다.
dpR = [1] * n
for pivot in range(n-1,-1,-1) :
  for i in range(n-1,pivot,-1) :
    if arr[i] < arr[pivot] :
      dpR[pivot] = max(dpR[pivot], dpR[i]+1)
# print(dpR)

# dpL과 dpR의 합을 구한뒤 -1을 하자
 # 1의 값은 중복되기 때문에 빼줘야 한다
for i in range(len(dpL)) :
  dpR[i] = dpL[i] + dpR[i]

print(max(dpR)-1)

# 풀이

[백준11053&파이썬] DP를 이용하여 반복문을 하나 줄일 수 있다.

• 가장 긴 부분수열을 구하는 문제를 그대로 응용 한다면 쉽게 풀 수 있다.
• 특정 수 S(k)에서 왼쪽과 오른쪽 모두 가장 작은 수들로 수열을 만들어야 한다.
• 두 방향으로 하여금 S(k)보다 작은것들의 개수를 DP를 활용하여 세어준다.
• 왼쪽 한번 ==> dpL , 오른쪽 한번 ==> dpR을 수행하고 dpL과 dpR을 더해준 후 1을 뺴줘야 한다.
• 1은 겹치기 때문이다.