# [Gold IV] 비 단조성 [문제 링크](https://www.acmicpc.net/problem/4237) ## 문제 설명 <p> 1부터 n까지 정수 n개로 이루어진 길이가 n인 수열 A가 있다. 수열의 각 원소는 서로 다르다. 이때, 다음과 같은 조건을 만족하는 수열 B를 찾으려고 한다.</p> <p> B[0] > B[1] < B[2] > B[3] < ...</p> <p> B는 A의 부분 수열이고, 위의 조건을 만족하는 수열 중 가장 길이가 긴 수열이다. 부분 수열이란 수열에서 원소 몇 개를 삭제해서 얻을 수 있는 수열이다. 이때, 순서는 항상 유지되어야 한다.</p> <p> A가 주어졌을 때, B의 길이를 구하는 프로그램을 작성하시오.</p> ## 입력 <p> 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 50이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 다음과 같은 형식이다.</p> <p> n A[0] A[1] A[2] ... A[n-1]</p> <p> n은 최대 30000이다. </p> ## 출력 <p> 각 테스트 케이스에 대해서, B의 길이를 출력한다. </p> ## 풀이 모든 수가 1번씩만 등장하는 수열이기 때문에 세 번 연속으로 증가하는 경우 가장 큰 원소를 마지막으로 남기는 것이 그리디하고, 세 번 연속으로 감소하는 경우 가장 작은 원소를 마지막으로 남기는 것이 그리디하다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; int llast=n+1, last=-1, cnt=0; while(n--) { int cur; cin >> cur; if(llast<last && last>cur || llast>last && last<cur) cnt++; llast=last; last=cur; } cout << cnt << '\n'; } } ```