[백준] 11054번 가장 긴 바이토닉 부분 수열 (Python)

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

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

---

풀이과정

①문제 들여다보기

이 문항은 앞전에 푼 11053문제에서 아주 살짝 업그레이드 된 버전의 문제이다.

https://stopmin.tistory.com/46

[백준] 11053번 가장 긴 증가하는 부분수열 (Python)

저 문제는 다만 증가하는 부분만 찾으면 되지만 이번 문항은 감소하는 부분까지 찾아야한다.

 

②아이디어 펼치기

11053번에서 짰던 코드로 먼저 arr을 탐색해 up_dp를 만들어준다. 이 리스트는 증가하는 부분을 탐색한 리스트!

arr을 반대로 탐색하면서 증가하는 부분을 찾는다. 이 리스트는 감소하는 부분을 탐색한 리스트가 된다.

그럼 증가하는 부분 리스트 up_dp와 감소하는 부분 down_dp가 만들어진다.

두 리스트의 각 항을 더해서 -1씩 해주면 max(dp)가 구하는 값이 된다.

위의 그림은 그 이유를 직관적으로 보여준다!

 

굳이 좀 더 코멘트를 달자면, up_dp를 통해서 알 수 있는 점은,

1. 해당 index에 있는 값으로 수열이 끝날 때 만들 수 있는 가장 긴 증가하는 수열의 길이
2. 어디서 가장 큰지

를 알 수 있고,

down_dp를 통해서 알 수 있는 점은,

1. 해당 index에 있는 값으로 수열이 끝날 때 만들 수 있는 가장 긴 감소하는 수열의 길이
2. 어디서 가장 큰지

이다. 

 이때  up_dp와 down_dp을 통해 알 수 있는 점 중 1번의 성질덕분에 이 문제가 해결되는 것이다. 왜냐하면, up_dp + down_dp - 1로 쾅 계산해보면 증가하다 감소하는 꺾이는 부분, 즉 산봉오리를 구할 수 있게 되기 때문이며, 이와 함께 그저 감소하는 수열이나 그저 증가하는 수열도 잡아먹게 되기 때문이다.

그렇기에! max(dp)값이 정답이 되는 것이다.

 

③최종코드

N = int(input())
array = list(map(int,input().split()))
dp = [0 for _ in range(N)]
for i in range(N):
    for j in range(i):
        if array[i] > array[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1

d = [0 for _ in range(N)]
for i in range(N-1,-1,-1):
    for j in range(N-1,i,-1):
        if array[i] > array[j] and d[i] < d[j]:
            d[i] = d[j]
    d[i] += 1

for i in range(len(dp)):
    dp[i] += d[i]
    dp[i] -= 1

print(max(dp))