# [Silver II] 안정적인 구간 [문제 링크](https://www.acmicpc.net/problem/33704) ## 문제 설명 <p>길이가 $N$인 배열 $A$가 주어진다. 길이가 $2$ 이상인 연속된 부분 배열 $B = left{A_i, A_{i+1}, cdots, A_j ight}$가 다음 조건을 만족하면, 쿠는 구간 $left[i,j ight]$에서 안정감을 느낀다.</p> <ul> <li>$K$를 $B$의 길이라고 할 때, $B$의 $leftlceil frac{K}{2} ight ceil$번째 원소의 값과 $B$를 오름차순으로 정렬했을 때의 $leftlceil frac{K}{2} ight ceil$번째 원소의 값이 같다.</li> </ul> <p>배열 $A$에 쿠가 안정감을 느낄 수 있는 구간이 존재하는지 판별해 보자.</p> ## 입력 <p>첫째 줄에 배열 $A$의 길이 $N$이 주어진다. $left(2leq Nleq 100, 000 ight)$</p> <p>둘째 줄에 $N$개의 정수 $A_1,, A_2,, cdots,, A_N$이 공백으로 구분되어 주어진다. $left(1leq A_ileq 10^9 ight)$</p> ## 출력 <p>배열 $A$에 쿠가 안정감을 느끼는 구간이 존재한다면 <span style="color:#e74c3c;"><code>YES</code></span>를, 그렇지 않다면 <span style="color:#e74c3c;"><code>NO</code></span>를 출력한다.</p> ## 예제 입력 1 <pre>4 4 2 1 3</pre> ## 예제 출력 1 <pre>YES</pre> ## 예제 입력 2 <pre>2 4 3</pre> ## 예제 출력 2 <pre>NO</pre> ## 풀이 #### B와 정렬했을 때의 B의 $leftlceil frac{K}{2} ight ceil$번째 값이 같은 부분수열이 있는지를 확인하면 된다. 이를 가장 작은 부분수열로 나타내보면 B의 길이가 2일때 B₁ ≤ B₂, B의 길이가 3일때 B₁ ≥ B₂ ≥ B₃ 인 경우 이 2가지가 전체 경우를 커버한다. ``` c++ #include<bits/stdc++.h> using namespace std; int arr[100000]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=0;i<n;i++) cin >> arr[i]; for(int i=0;i<n-1;i++) { if(arr[i]<=arr[i+1] || i+2<n && arr[i]>=arr[i+1] && arr[i+1]>=arr[i+2]) { cout << "YES"; return 0; } } cout << "NO"; } ```