[백준/파이썬] 11054번 가장 긴 바이토닉 부분 수열

solved.ac Class 4레벨에 속한 문제이다.

문제 주소: https://www.acmicpc.net/problem/11054

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

문제 해석

문제 풀이

입력 범위가 1000 이기 때문에, lis 알고리즘이 아니라 2차원 dp를 사용해 가장 긴 증가하는 수열을 앞에서, 뒤집어서 두 번 구해주었다.

뒤집어서 구해준 값들을 다시 뒤집어 순서를 맞춰주고, 두 dp값들의 합이 최대가 되도록 하는 값 + 1이 답이 된다.

문제 코드

def solve(n, arr):
	# 앞에서 부터 가장 긴 증가하는 수열 구하기 
    dp = [0] * n
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[j] + 1, dp[i])
                
	# 뒤집어서 가장 긴 증가하는 수열 구하기 
    dp_back = [0] * n
    arr_back = arr[::-1]
    for i in range(1, n):
        for j in range(i):
            if arr_back[i] > arr_back[j]:
                dp_back[i] = max(dp_back[j] + 1, dp_back[i])
	# 구한 두 dp값들이 최대가 되는 값 구하기
    answer = 0
    for i in range(n):
    	# 뒤에서 부터 구한 값들은 다시 뒤집어서 최댓값 갱신
        answer = max(answer, dp[i] + dp_back[::-1][i])
    return answer + 1

# input
n = int(input())
arr = list(map(int, input().split()))
print(solve(n, arr))

제출 결과