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

출처 : 

https://www.acmicpc.net/problem/11054

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

 

풀이 :

n = int(input())

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

inc = [1 for i in range(n)]

for i in range(n):
    for j in range(i):
        if a[i] > a[j]:
            inc[i] = max(inc[i], inc[j]+1)
            
dec = [1 for i in range(n)]

for i in range(n-1, -1, -1):
    for j in range(n-1,i,-1):
        if a[i] > a[j] :
            dec[i] = max(dec[i], dec[j]+1)
            
rlt = [0 for i in range(n)]

for i in range(n):
    rlt[i] = inc[i]+dec[i] - 1
    
print(max(rlt))

 

dp 너무 어렵다... 이해하고 보면 근데 할 만 하긴한데... 이제 진지하게 코테좀 집중해야겠다..

 

문제의 원리부터 살펴보자.

수열 이 커졌다가 작아지는 것을 만족하는 수열을 바이토닉 수열이라고 한다. 

문제에서 응용하면 

1 5 2 1 4 3 4 5 2 1 중에서 

증가하는 수열

1 2 3 4 5

내려가는 수열 

5 2 1 

이렇게 찾을 수 있다.

 

그렇다면 결국 1234521 을 찾아 5+3-1 = 7 이라는 값을 찾아줘야한다.

 

이거 올라가는 수열과 내려가는 수열의 합이 최대인 결과를 찾아줘야 하므로 앞에서 푼 11053 문제를 이용해서

증가 dp

1 2 2 1 3 3 4 5 2 1

감소 dp

1 5 2 1 4 3 3 3 2 1

합

2 7 4 2 7 6 7 8 4 2

에서 8 -1 =7 을 답으로 제시하면 된다.

 

이걸 이제 코드로 옮기자.

 

증가 dp 는 이전 11053 과 똑같은 코드로 짜준다. 

i 번째값이 j 번째 값(i의 이전값)보다 크다면 inc 값에 1을 더해주거나 가장 큰 값을 저장해준다.

 

감소dp는 수열을 거꾸로 만들어서 위와 같이진행 시켜준다.

 

그 다음 합의 결과를 구한다음 -1 을 해준다음 큰 수 를 찾아준다.