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

 

n = int(input())

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

dp1 = [0] * n
dp2 = [0] * n
for i in range(n):
    dp1[i] = 1
    for j in range(i):
        if num[j] < num[i]:
            dp1[i] = max(dp1[i], dp1[j] + 1)

num.reverse()
for i in range(n):
    dp2[i] = 1
    for j in range(i):
        if num[j] < num[i]:
            dp2[i] = max(dp2[i], dp2[j] + 1)
dp2.reverse()

ans = [0] * n
for i in range(n):
    ans[i] = dp1[i] + dp2[i] - 1
print(max(ans))

 

코드 설명

바이토닉 수열을 구하기 위해 dp1 ,dp2 리스트를 n 길이만큼 만들어 준다.

반복문을 정방향으로 진행하면서 내부 반복문을 통해 숫자가 증가하는 경우에만 카운트를 해준다.

반대쪽으로 증가하는 수열을 찾기 위해서 배열을 뒤집어 준다.

그 후 똑같은 연산을 수행한다. dp1, dp2에 저장된 값을 서로 더해주고 -1 을 해준다. -1은 같은 수가 중복되기 때문이다.

가장 큰 값을 출력하며 종료한다.

 

Point : LIS 알고리즘과 매우 유사하다. 왼쪽부터 오른쪽으로 증가하는 수를 저장한 dp1, 오른쪽부터 왼쪽으로 진행하며 증가하는 수를 저장한 dp2 를 이용한다. 두개의 리스트를 각 index와 더하고 -1 을 해주면 바이토닉 수열을 찾을 수 있다.