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

문제링크 : https://www.acmicpc.net/problem/11054

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

 

작성코드

 

 

 

해설

 

11053 문제 (https://yellowtail2357.tistory.com/40)

[백준] 11053 가장 긴 증가하는 부분 수열 (python 파이썬)

 

의 변형문제이다.

 

가장 긴 증가하는 부분 수열의 경우 랭크 == 길이였다.

바이토닉 수열의 양쪽에서 증가 수열이 진행되어 합이 가장 큰 랭크가 된다.

 

예제 입력으로 주어진 {1, 5, 2, 1, 4, 3, 4, 5, 2, 1}의 합 랭크를 아래와 같은 그래프로 표현할 수 있다.

이 합 랭크 그래프는 해당 숫자의 앞 뒤 랭크 길이가 되므로 해당 수를 바이토닉 수열의 최고점(k)로 둔다면 해당 수의 바이토닉 수열 길이를 알 수 있다.

 

하지만 두 랭크의 합이기 때문에 모든 시작 랭크가 2가 되어 합 랭크에서 -1 을 해주어야 바이토닉 수열의 길이가 된다.

 

가장 긴 바이토닉 수열을 찾으려면 이 중에서 가장 랭크 합이 큰 수 -1을 해주면 답이 된다.

 

이 내용을 코드로 작성한다면

이와 같이 나온다.

 

역순 랭크를 구하기 위해 기존 리스트를 reversed 하여 랭크를 구해주고 이 랭크는 뒷 숫자부터 랭크이기 때문에

다시 랭크를 reverse해주어 두 랭크 합 -1 을 해주면 바이토닉 수열의 랭크가 나온다.