BOJ 20127 - Y-수열 [C++]

 

 

문제

https://www.acmicpc.net/problem/20127

 

길이가 $N$인 수열 $A$가 주어지면,

앞의 $K$개 원소를 맨 뒤로 옮겨서 단조수열을 만들 수 있는지 판단하고 가능하다면 $K$의 최솟값을 찾아야 한다.

풀이

증가하는 횟수를 누적한 배열 $P$와, 감소하는 횟수를 누적한 배열 $Q$를 생각해보자.

 

$P[i] = P[i-1] + \begin{cases} 1 & A[i] - A[i-1] \geq 0 \\ 0 & \text{otherwise} \end{cases}$

 

$Q[i] = Q[i-1] + \begin{cases} 1 & A[i] - A[i-1] \leq 0 \\ 0 & \text{otherwise} \end{cases}$

 

우선, $P[N]$ 혹은 $Q[N]$이 $N$과 같다면 답은 $0$이다.그렇지 않다면, $N$보다 작은 어떠한 $K$에 대해 단조수열을 만들 수 있는지 확인해야 한다.

 

증가수열을 만들 수 있을 조건부터 생각해보자.

 

● $A[1]$이 $A[N]$의 뒤에 위치하게 되므로 $A[N] \leq A[1]$이어야 한다.

 

● 구간 $[1,K]$에서 $A$는 증가해야 한다. $\rightarrow P[K] = K$

 

● 구간 $[K+1,N]$에서 $A$는 증가해야 한다. $\rightarrow P[N] - P[K+1] = N-K-1$

 

감소수열을 만들 수 있을 조건도 위와 비슷하게 판별해주면 된다.

 

#include <iostream>
using namespace std;

int P[1000001]{ 0,1 }, Q[1000001]{ 0,1 }, S, E, N, p;
int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> N >> S;
    p = S;
    for (int i = 2; i <= N; i++) {
        cin >> E;
        P[i] = P[i - 1] + (E - p >= 0);
        Q[i] = Q[i - 1] + (E - p <= 0);
        p = E;
    }
    if (P[N] == N || Q[N] == N) return cout << 0, 0;
    for (int K = 1; K < N; K++) if ((P[N] - P[K+1] == N - K - 1 && P[K] == K && E <= S) || (Q[N] - Q[K+1] == N - K - 1 && Q[K] == K && E >= S)) return cout << K, 0;
    cout << -1;

}