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

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

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

 

 

가장 긴 바이토닉 수열이란 a1<a2<...ak-1<ak<ak+1>...an-1>an을 만족하는 수열로 가장 긴 증가수열 + 감소수열을 구하는 문제다. 

 

DP를 이용하여 문제를 풀고자 하였고, LIS를 이용하여 1, n까지의 i와 i까지의 j를 이용하여 최대 증가 수열의 길이를 dp에 저장하도록 진행하였다. 반대로 i번째까지의 감소 수열의 최대 길이는 배열을 역순으로 지정하여 반영되도록 하였다. 즉 끝에서 부터 i 번째까지 최대 감소 수열의 길이를 나타낸다. 

배열이 역순이므로 기존 배열에서의 i번째 수는 역순 배열의 n-i-1번째 수가 된다. 여기서 주의할 점은 모두 최대 증가 수열 및 최대 감소 수열 모두 i를 포함하므로 -1을 해주어야한다는 것이다. 

n = int(input())
numbers = list(map(int, input().split()))
reversed_numbers = numbers[::-1]
dp1 = [1]*n
dp2 = [1]*n

for i in range(n):
    for j in range(i):
        if numbers[i] > numbers[j]:
            dp1[i] = max(dp1[i], dp1[j]+1)
        if reversed_numbers[i] > reversed_numbers[j]:
            dp2[i] = max(dp2[i], dp2[j]+1)

result = [(dp1[i]+dp2[n-1-i]-1) for i in range(n)]
    
print(max(result))

 

 

 

( 풀이에 참고한 사이트 )

https://seohyun0120.tistory.com/entry/%EB%B0%B1%EC%A4%80-11054-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EB%B0%94%EC%9D%B4%ED%86%A0%EB%8B%89-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-%ED%92%80%EC%9D%B4

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