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

문제

 

 

 

이 문제를 보고 처음 생각이 든 알고리즘은 LIS이다.

그러나 문제는 최장 증가 부분수열이 아니라 바이토닉수열로 어떤 수를 기준으로 오른쪽 부분은 감소하는 부분수열도 찾아주어야한다.

 

 

그래서 생각한 방법은 최장증가 부분수열을 구하고 최장감소 부분수열을 구해서 이 둘의 합이 최대가 되는 지점을 찾아주는 것이다.

 

 

 

정답코드

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

ans = 0
dp1 = [0] * n
dp2 = [0] * n

#최장 증가 부분수열
for i in range(n):
    dp1[i] = 1
    for j in range(i):
        if a[i] > a[j]:
            dp1[i] = max(dp1[i],dp1[j]+1)
#최장 감소 부분수열
for i in range(n-1,-1,-1):
    dp2[i] = 1
    for j in range(n-1,i,-1):
        if a[i] > a[j]:
            dp2[i] = max(dp2[i],dp2[j]+1)

for i in range(n):
    #기준점이 되는 부분의 길이가 두번 더해졌으므로 -1을 한번 해줌
    ans = max(ans,dp1[i]+dp2[i]-1)
print(ans)
# print(dp1)
# print(dp2)

 

 

이때 dp1[i]=1 과 같이 시작점 부분부터 길이를 측정하므로 1부터 길이를 계산했는데 둘이 합쳐서 ans를 구할 때 이 부분이 두번 계산됐으므로 -1을 해주었다.

 

 

골드4 레벨 문제를 풀면서 느끼는 점은 기존에 풀었던 문제와 푸는 방식이 유사한데 이를 어떻게 응용해서 문제에 적용할 지 생각해내는 것이 가장 중요한 것 같다.