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

이제 dp같은경우는 하루에 한문제씩은 반드시 풀고 있고 또 코드를 쓰는 시간보다 생각해야하는 시간이 길기에 대부분 알바하면서 푸는것같아서 포스팅을 자주 못하고 있다.

 

따라서 알바하면서 푼거는 전부 포스팅하지는 않고 그 중에 좀 까다로웠던 문제 위주로 포스팅하고자 한다.

 

뭐 아무튼 가장 긴 바이토닉 부분 수열문제이다.

 

dp문제가 으레 그렇듯 보자마자는 도대체 어떻게 접근해야할지 모르겠었으나 생각을 좀 해보니

가장 긴 증가하는 부분수열과 가장 긴 감소하는 부분수열의 합이라는 생각이 들었고 이에 코드로 작성해보았다.

import sys

n=int(sys.stdin.readline().rstrip())
numbers=list(map(int,sys.stdin.readline().rstrip().split()))
lis=[0]*n
lds=[0]*n

lis[0]=1
lds[n-1]=1
result=0
for i in range(1,n):
    lis_max=0
    for j in range(i):
        if numbers[i]>numbers[j]:
            lis_max=max(lis_max,lis[j])
    lis[i]=lis_max+1
for i in range(n-1,-1,-1):
    lds_max=0
    for j in range(n-1,i,-1):
        if numbers[i]>numbers[j]:
            lds_max=max(lds_max,lds[j])
    lds[i]=lds_max+1

result=0
for i in range(n):
    result=max(lis[i]+lds[i],result)
print(result-1)

가장 긴 증가수열을 구하고 또 가장 긴 감소수열을 또 구해준다. 다만 감소 수열은 탑다운이라고 부르는게 맞을 듯하다.

뭐 아무튼 구하고 난 뒤 그 합이 최고가 되는 값을 출력하는데 중요한건 -1을 해야한다는 것이다.

왜냐면 자기 자신이 2번 포함되기 때문이다.