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

이전 문제에서 O(n^2)코드를 사용해도 시간 초과가 뜨지 않는 것을 알았기 때문에, 이번 문제에서는 코드가 좀 더 깔끔하게 짜기 위해서 O(n^2)코드를 사용했다. 

 

바이토닉 부분 수열은 한 수열 안에서 증가하는 부분과 감소하는 부분이 존재하는 수열이다. 증가하거나 감소하는 부분이 둘 중 하나 없어도 바이토닉 수열이라고 할 수 있다.

 

바이토닉 부분 수열 자체가 증가하는 부분과 감소하는 부분이 결합된 형태이다보니 그냥 한번 각 경우에 따른 dp를 구해보고 꺾이는 부분(변곡점이랄까)은 무엇이 다른가를 봤는데 두 dp의 합이 가장 큰 것을 알 수 있었다. 즉, 증가하는 부분의 길이와 감소하는 부분의 길이의 합이 가장 큰 것이 가장 긴 바이토닉 부분 수열이었던 것이다.

 

그러므로 두 부분의 dp를 각각 구해준 뒤 합을 구해주고 꺾이는 부분이 겹치기 때문에 1을 빼주면 된다.

##변수 선언 부분##
A = []
dp_up = []
dp_down = []
dp_max = []
##메인 함수 부분##
if __name__ == "__main__":
    N = int(input())
    A = [int(x) for x in input().split()]
    dp_up = [1 for x in range(N)] #증가하는 부분 수열을 구하기 위한 dp
    dp_down = [1 for x in range(N)] #감소하는 부분 수열을 구하기 위한 dp
    for i in range(N): #증가하는 부분 수열 구하기
        for j in range(i):
            if A[i] > A[j]: #이전 값이 자신보다 더 작으면
                dp_up[i] = max(dp_up[i], dp_up[j]+1) #이전부터 순회하면서 갱신한 값과 특정 값+1중에 큰 값을 갱신

    for i in range(N-1,-1,-1): #감소하는 부분 수열 구하기
        for j in range(i,N): #N-1부터 시작하면서 거꾸로 구해주면 된다.
            if A[i] > A[j]:
                dp_down[i] = max(dp_down[i],dp_down[j]+1)

    for i in range(N): #두 dp의 각 원소의 합을 dp_max배열에 저장해준다.
        dp_max.append(dp_up[i]+dp_down[i]-1)

    print(max(dp_max))

 

꺾이는 부분의 특징을 찾으면 쉽게 풀 수 있었던 문제이다. 골드3 문제였는데, 오히려 이전 11053번을 O(nlogn)으로 문제를 냈으면 그게 더 어려웠지 않을까 싶다.