백준풀이 가장긴바이토닉수열 파이썬

먼저 바이토닉수열이란게 뭘까?

난 봉우리(꼭대기)를 가지고 있는 수열로 이해했다

 

4 3 2 1: 4가 꼭대기이다

1 2 3 4 5 4 3 2 1: 5가꼭대기이다

5 4 3 2 1: 5가 꼭대기이다

 

즉 꼭대기를 중심으로 증가수열과 감소수열이 완성된다

꼭대기는 배열의 양끝에도 올수있으며  이때는 단순한 증가수열 또는 감소수열이 된다

 

접근방식은 

어떤곳에서 바이토닉 수열을 만들던 항상 꼭대기는 존재하기때문에 

배열의 어떤 부분이 꼭대기가 되었을때 가장 긴 바이토닉 수열이 완성되는가에 있다

 

그리고 배열의 어떤한부분을 꼭대기로 가질때의 바이토닉함수의 길이는

어떤한부분의 인덱스를 3이라고했을때

 

3까지의 최대 증가수열길이 + 3부터 시작하는 최대감소수열길이 -1이다 

 

이걸 구현해보면

# 끝나는 지점에서의 증가함수
N=int(input())
d1=[1 for i in range(N)]
d2=[1 for i in range(N)]
a=list(map(int,input().split()))
for i in range(N):
    z1=[0]
    z2=[0]
    for j in range(i):
        if a[i] > a[i-j-1]:
            z1.append(d1[i-j-1])
        if a[N-i-1] > a[N-i-1+j+1]:
            z2.append(d2[N-i-1+j+1])
    d1[i]=max(z1)+1
    d2[N-i-1]=max(z2)+1
# print(d1)
# print(d2)

c=[d1[i]+d2[i]-1 for i in range(N)]
print(max(c))

요런모양이된다

 

가장긴 증가수열과 가장긴 감소수열을 합쳤다

기본예제는 통과한모습 일단 제출해본다 근데 왜 시간초과가 뜰것같지?

 

엥 이걸 통과한다고? 감사합니다...감사합니다...

롤하러가야지