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

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

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

이전에 보았던 가장 긴 부분증가 수열과 비슷한 느낌의 DP 문제이다

가장 긴 부분증가 수열은
2중 반복문을 돌며,
‘현재’ 가진 값보다 ‘이전’에 있었던 값이 작다면,
해당 부분의 dp를 가져와 +1 더한값과 현재값을 비교하였다

또한 바이토닉 수열은
증가 후, 점진적으로 내려가는 수열까지도 포함하므로
dp 테이블을 하나 더 잡아
‘역’으로 돌려주었다

이후 ‘두 dp의 각 요소의 합 -1’(2번 dp 비교를 하였기에 자기 자신의 숫자가 중복)
을 비교하여 산출한 것중 가장 큰 값을 출력하였다

결국 중간에 ‘증가 수열’이라는 부분이 있기에 ‘처음부터’ 세면서 올라올 필요가 있기는 하였다

Code

import sys
inp = sys.stdin.readline

num = int(inp().strip())

val = list(map(int,inp().split()))
dp1 = [1 for _ in range(num)]
dp2 = [1 for _ in range(num)]

# 앞으로 돌기
for i in range(num):
    for j in range(i):
        if val[i] > val[j]:
            dp1[i] = max(dp1[i],dp1[j] + 1)

# 뒤로 돌기
for i in range(num-1,-1,-1):
    for j in range(num-1,i-1,-1):
        if val[i] > val[j]:
            dp2[i] = max(dp2[i],dp2[j] + 1)

mv = 0

for i in range(num):
    mv = max(dp1[i] + dp2[i] -1,mv)

print(mv)

해결 아이디어

1. dp1 : 가장 긴 부분 증가 수열
   dp2 : 뒤집어서 본 가장 긴 부분 증가 수열
   
2. 따라서 i요소의 ‘가장 긴 바이토닉 수열’의 길이는
   dp1[i] + dp2[i] - 1 이므로
   dp1 과 dp2의 테이블을 채운뒤 max를 구하면 된다
   
3. 부분 증가 수열의 개수는
   처음부터 현 시점까지, ‘해당 요소’가 작다면
   그 부분의 dp값 + 1 을 해준값과 ‘현재’ dp값을 비교하여 큰 쪽을 대입하는 방식으로 구한다
   
4. 뒤집어서도 구한 후
   max 연산하여 마무리