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

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

 

부분 수열 시리즈 문제이다. 당연히 dp 문제이다. 하지만 추가로 조건이

증가하는 부분수열 + 감소하는 부분 수열을 더해서 가장 긴 부분 수열을 찾는 것이다.

import sys
input = sys.stdin.readline

N = int(input())
s = list(map(int,input().split()))
reverse_s = s[::-1]
dp = [1] * N
reverse_dp = [1] * N

for i in range(N):
    for j in range(i):
        if s[j] < s[i]:
            dp[i] = max(dp[i], dp[j] + 1)
        if reverse_s[j] < reverse_s[i]:
            reverse_dp[i] = max(reverse_dp[i], reverse_dp[j]+1)

result = []
for i in range(N):
    result.append(dp[i] + reverse_dp[N-i-1] - 1)
print(max(result))

 

회고.

반대로 된 배열을 만들어 하나의 for문으로 하는 것은 좋았으나, 거꾸로 만든 배열을 증가하는 부분수열 + 감소하는 부분 수열 하는 과정에서 다시금 N-i-1을 해주므로써, 정상 배열 방향처럼 맞춰줬어야 했는데 안했다...

또한,  증가하는 부분수열 + 감소하는 부분 수열을 하는 과정에서 중앙에 있는 값은 2번 더해졌으므로 1번 빼줬어야 했는데 안했다.... 

아직 다중 조건을 따는 부분이 미흡한거 같다,...