문제 링크https://www.acmicpc.net/problem/25571 문제 요약길이가 \(N\)인 배열이 주어졌을 때, 만들 수 있는 연속된 부분배열들 중 지그재그인 부분배열의 개수를 찾는 문제이다. 배열이 지그재그라는 뜻은 배열의 원소가 감소와 증가 또는 증가와 감소를 반복하는 배열을 의미한다. 문제 풀이만들 수 있는 모든 부분배열 \(A[lo, hi]\)에 대해서 지그재그인지 검사하면 답을 구할 수 있다. 하지만 이 방법은 시간복잡도가 \(\mathcal {O}(N^2)\)이라서, \(N\)이 10만 일 때 제한시간 내에 문제를 해결하지 못하므로 더 효율적인 풀이가 필요하다. 지그재그 부분배열의 특징을 살펴보면 \(A[lo, hi - 1]\)이 지그재그이고, \(A[lo, hi]\)가 지그재..
