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

문제

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

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

www.acmicpc.net

이 문제는 가장 긴 증가하는 부분 수열 문제를 응용하는 문제입니다.
https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

왼쪽에서 오른쪽으로 증가하는 부분 수열의 길이를 구하고,
오른쪽에서 왼쪽으로는 감소하는 부분 수열의 길이를 구해줍니다.

그 이후 이 수열을 합쳐주면 바이토닉 수열을 구할 수 있습니다.

예를들어 [1, 2, 1, 5, 2] 라는 수열이 있다면,
왼쪽에서 오른쪽으로 증가하는 부분 수열의 길이는 [1, 2, 1, 3, 2] 가 될 것입니다.
오른쪽에서 왼쪽으로 감소하는 부분 수열의 길이는 [3, 2, 2, 1, 1] 가 될 것입니다.

이 수열을 합쳐주면 [4, 4, 3, 4, 3] 입니다.

이 길이 중 가장 큰 길이에서 1을 빼준 값이 가장 긴 바이토닉 부분 수열의 길이입니다.

왜 그럴까요?
첫번째 4를 보시면 증가하는 부분수열의 길이는 1로, [1] 하나입니다.
감소하는 부분수열은 [1, 2, 5]로 3입니다.
1이 중복되기 때문에 1을 빼주어야 합니다.

감소하는 부분 수열을 편하게 구하기 위해 array를 뒤집어서 감소하는 수열을 구해준 후, 감소하는 수열도 다시 뒤집어줬습니다.

증가하는 부분 수열의 길이를 구하고, 감소하는 부분 수열의 길이까지는 구하였는데,
증가하는 부분 수열의 길이와 감소하는 부분 수열의 길이를 합쳐서 바이토닉 수열의 길이를 알아낼 수 있는지에 대해서
쉽게 떠올리지 못했던 문제였습니다.