11054 - 가장 긴 바이토닉 수열

다이나믹 프로그래밍 문제를 풀면서 Long Increase Subsequence(가장 증가하는 긴 수열) 문제를 풀고 연관된 문제로 골드4문제가 보이길래 바로 풀어보았다.

처음에는 한개의 최댓값 기준을 정해 LIS와 LDS를 나누어서 써보았지만, 시간초과가 발생하였다.

그러던 중 LDS문제를 LIS를 Reverse해서 해결하는 풀이법을 보게 되었다. 

그래서 이 문제에도 Reverse를 적용시켜 보았다. 

import sys
#sys.stdin = open("/Users/positive/Desktop/무제 폴더/Algorithm/230106/11054in.txt","r")
input = sys.stdin.readline

N = int(input())

arr = list(map(int, input().split()))

dp_i = [1 for _ in range(N)]
dp_d = [1 for _ in range(N)]

dp=[0]*N

for i in range(N):
    for j in range(i):
        if arr[i] > arr[j]:
            dp_i[i] = max(dp_i[i], dp_i[j]+1)

arr.reverse()

for i in range(N):
    for j in range(i):
        if arr[i]>arr[j]:
            dp_d[i]=max(dp_d[i],dp_d[j]+1)
dp_d.reverse()
for i in range(N):
    dp[i]=dp_i[i]+dp_d[i]

print(max(dp)-1)

1. 먼저 주어진 배열에 LIS를 적용시켜 최대 증가를 구한다. 그리고 그 값을 dp_i에 저장을 한다

2. 다음은 dp를 reverse하여 다시 LIS를 적용한다. 그렇게 되면 dp도 reverse된 상태로 저장이 되기때문에

dp_d도 reverse를 해준다.

3. dp_i와 dp_d의 각 index의 값을 더해서 1을 빼면(index가 2번 Count되었기 때문에 ) 그 Index를 최곳값으로 선택했을때

바이토닉 수열의 길이가 나오게 된다. 그 값을 dp에 저장하고

4.dp의 최댓값을 출력하게 되면 바이토닉수열의 최장길이가 도출되게 된다

 

이 문제를 가장 처음 접했을때에는 최곳값의 index를 찾아내어 그 index기준으로 양옆으로 lis lds를 사용하려 했지만

reverse를 활용하면 더욱 더 간단하게 풀이된다는것을 알았다.