[파이썬] 11054 가장 긴 바이토닉 부분 수열

 

11053 문제에이어 나오는 문제이다

 

11053에서는 예시인

 

[1 5 2 1 4 3 4 5 2 1]

 

에서 증가하는 수열인 [1 2 3 4 5]

 

를 찾는거였다면 이번에는 5까지 증가 후 줄어드는 2, 1까지 포함시켜

 

[1 2 3 4 5 2 1]을 찾는 문제이다 

 

경우의 수는 2가지가있다

 

[1 5 2 1 4 3 4 5 2 1]

[1 5 2 1 4 3 4 5 2 1]

 

 

위는 7, 아래는 6이다

 

사실 우리는 한방에 찾을 필요가 없다

 

증가하는 최댓값 + 감소하는 최댓값을 하면 그게 답이다 

 

일단 코드를 보자 

 

n=int(input()) ary=list(map(int, input().split()))  dp=[1]*n r_dp=[1]*n ans = [0]*n for i in range(n):    for p in range(i):     if ary[p]<ary[i]:           dp[i]=max(dp[i],dp[p]+1) for i in range(n, -1, -1):      for p in range(n-1, i, -1):         if ary[p]<ary[i]:               r_dp[i]=max(r_dp[i],r_dp[p]+1) for i in range(n):      ans[i] = dp[i] + r_dp[i] -1 print(max(ans))

 

먼저 11053처럼 코드를 짜고

 

이번에는 역순으로 ary를 한번 더 검사해서 새로운 dp에 넣어준다 (r_dp)

 

그럼 두 dp 값은 이렇게 나올 것이다

ary값이 이하와 같을 때

ary =  [1, 5, 2, 1, 4, 3, 4, 5, 2, 1]

 

dp =   [1, 2, 2, 1, 3, 3, 4, 5, 2, 1]

 

r_dp = [1, 5, 2, 1, 4, 3, 3, 3, 2, 1]

 

그럼 결국 1, 2, 3, 4, 5 값이 dp,

뒤에서 올라오는 1, 2, 5 값이 자연스레 max값이 될 것이고

 

 

두 dp값을 합해서 이걸 이어주면 1, 2, 3, 4, 5, 5, 2, 1

 

ans에 넣어주고 

 

5는 필요 없으니 -1

 

ans의 max값을 뽑아내면 이 문제의 답이 된다

 

 

역시.. 선구자들은 머리가 비상한 게 분명하다.. 

 

문제를 풀면서 아직도 아리송하다 싶으면 

꺼무위키에 최장 증가 부분 수열을 쳐서 읽어보자

 

더욱더 잘 이해가 갈 것이다