[백준] 20192번: 순서 섞기

www.acmicpc.net/problem/20192

20192번: 순서 섞기

문제 요약

정수 $N$개로 이루어진 배열 A가 주어진다. 이때, A에 대하여 다음 '순서 섞기' 연산을 수행한다.

 

A의 가장 앞쪽 또는 뒤쪽 원소를 떼어 내서 새로운 배열 B의 앞쪽부터 붙여나간다. A에 더이상 원소가 남아있지 않으면, B를 다시 A에 복사한다.

 

A를 단조증가하도록 만들기 위해 필요한 '순서 섞기' 연산의 최소 횟수를 구하여라.

제한

$1 \le N \le 300\ 000$

$1 \le A_i \le 10^9$

풀이

입력받은 수열 A가 처음부터 단조증가하는 상태라면 필요한 최소 연산 횟수는 당연히 0이다. 그렇지 않다면 최소 한 번은 연산을 수행해야 하는데, 연산을 정확히 한 번 수행하여 단조증가하도록 만들 수 있는 수열은 어떤 형태일까?

 

단조증가하는 어떤 수열 A에서 시작하여 순서 섞기 연산을 거꾸로 수행한다고 생각해 보자. A의 처음 원소부터 차례대로 새로운 수열 B의 가장 앞쪽 또는 뒤쪽에 붙여나간다. A가 단조증가하는 상태였으므로, B는 바깥쪽에서 안쪽으로 갈수록 원소들이 점점 커지는 형태가 될 것이라고 짐작할 수 있다. 물론 B를 단조감소하는 형태로 만드는 것도 가능하지만, B의 가장 앞에 음의 값을 갖는 가상의 원소 하나가 덧붙여져 있다고 생각하면 결국 앞 경우와 다를 것이 없어진다. 그림으로 나타내 보면 다음과 같다.

연산을 1회 적용하여 단조증가하도록 만들 수 있는 수열(오르막은 단조증가, 내리막은 단조감소 부분을 나타냄)

B를 단조감소하도록 만들었을 경우. 가장 앞(빨간 점 부분)에 음의 값을 갖는 원소 하나가 있다고 생각하면 위 경우와 결국 같다.

위 그림에서도 확인할 수 있다시피, 수열 중간에 극대가 되는 부분이 하나 존재하게 된다. 이러한 부분은 원소 하나로 이루어져 있을 수도 있고(예: 1 2 1), 같은 값을 갖는 원소들로 이루어져 있을 수도 있는데(예: 1 2 2 2 1), 후자의 경우 같은 원소 여러개를 하나로 묶어서 생각해도 무방하니 두 경우 모두 '극대점'이라고 부르기로 하자.

 

어떤 수열에 극대점이 하나 존재하는 경우 필요한 최소 연산 횟수가 1회임을 알았고, 이제 극대점이 2개 이상 존재하는 일반적인 경우를 살펴보자. 극대점이 여러 개 존재하는 수열이 입력으로 주어졌을 때, 순서 섞기 연산을 통해서 극대점의 개수를 줄이려면 어떻게 해야 할까? 우선, 주어진 수열의 맨 앞과 뒤에 음의 값을 갖는 원소를 하나씩 덧붙였다고 생각하면, 수열의 형태를 증가 → 감소 → 증가 → ··· → 감소하는 꼴로 일반화할 수 있다(다만 유의할 점은, 수열의 맨 뒤에 음의 원소를 붙여 수열의 마지막 부분이 감소하도록 할 때는 그 전에 감소하는 구간이 적어도 하나는 있어야 한다. 감소 구간이 없었다는 것은 수열이 이미 단조증가하는 상태라는 것이고, 이때 맨 뒤에 음의 원소를 덧붙이면 극대점을 하나 만들어 버리는 꼴이 된다). 예를 하나 그림으로 나타내 보면 다음과 같다.

극대점이 5개인 경우

이제 순서 섞기 연산을 다음처럼 수행한다.

 

1. 수열의 처음~첫 극대점까지의 단조증가 구간과, 마지막 극대점~수열의 끝까지의 단조감소 구간만을 고려하자. 전자는 앞에서 보았을 때 단조증가하고, 후자도 뒤에서 보았을 때 단조증가한다. 따라서 전자의 맨 앞 원소와 후자의 맨 뒤 원소 중 크지 않은 쪽을 선택하여 새로운 수열을 앞에서부터 채워나가고, 두 구간이 모두 비게 될 때까지 이를 반복하면(merge sort에서 merge연산을 수행하는 방식과 동일) 새로운 수열에는 단조증가 구간이 하나 생기게 된다.
2. 1번 단계를 반대로 수행한다. 즉, 수열의 처음~첫 극소점까지의 단조감소 구간과 마지막 극소점~수열의 끝까지의 단조증가 구간만을 고려하면, 전자는 앞에서 보았을 때 단조감소하고 후자도 마찬가지로 뒤에서 보았을 때 단조감소한다. 두 단조감소 수열을 하나의 단조감소 수열로 merge한 것이 새로운 수열에 추가되는데, 이때 1번 단계에서 2번 단계로 넘어가면서 극대점 하나가 생기게 됨을 알 수 있다.
3. 기존 수열이 완전히 비게 될 때 까지 1, 2번 단계를 반복한다.

그림으로 위 과정에 대한 예를 들어 보면 아래와 같다.

순서 섞기 연산 과정 예(왼쪽은 기존 수열, 오른쪽은 새로운 수열)

위 예처럼 극대점이 홀수개였을 경우 새로운 수열이 단조증가하며 끝나게 되는데, 그림에도 나와있듯 가상의 음수 원소를 맨 뒤에 덧붙여 놓았다고 생각하면 앞에서 일반화했던 수열의 형태에서 벗어나지 않는다.

 

이와 같은 방식으로 순서 섞기 연산을 수행하면 수열의 양 끝에서부터 양 끝 극대/극소점까지 원소를 떼어 나가는 동안 새로 만드는 수열에는 극대점이 발생하지 않게 되고, 극대점이 필연적으로 발생하게 되는 부분에서만(1번에서 2번 단계로 넘어갈 때) 발생하게 되므로 결국 새로운 수열에서 극대점의 수를 최소한으로 발생시키게 된다. 즉, 기존의 극대점 개수를 최대한으로 줄이게 되는 것과 같다.

 

문제에서 구하려는 것은 극대점의 수를 0으로 만들기 위해 필요한 최소 연산 횟수와 같고, 극대점이 $x$개 있었다면 최대한 줄였을 때 `ceil(x/2)`개가 된다는 것을 알 수 있으므로,

 

`(x`가 `1`이 될 때 까지 적용해야 하는 `ceil(x/2)`연산의 횟수`) + 1`

 

을 계산해 주면 된다(주의: `x=1`일 때 `ceil(x/2)=ceil(1/2)=1!=0`).

구현

수열의 원소들을 입력받는 동시에 극대점의 개수를 계산해 주었다. up은 현재 단조증가 상태이면 true, 단조감소 상태이면 false값을 갖는데, 만약 현재 단조증가하는 상태에서 마지막으로 입력받았던 원소보다 새로 입력받은 원소가 더 작다면 극대점이 하나 있다는 것이므로 극대점 개수를 저장하는 cnt값을 1만큼 증가시키고, 단조감소 상태로 바뀌었으므로 up을 false로 바꿔 준다. 반대로, 현재 단조감소하는 상태에서 마지막 입력값보다 현재 입력값이 더 크면 up을 true로 바꿔준다.

 

풀이에서 이야기했듯, 일반화된 수열의 형태는 단조증가하며 시작하는 꼴이므로 up의 초기값을 true로 설정하면 된다. 하지만 수열이 단조증가하며 끝나는 경우 수열의 끝부분을 극대점으로 세려면 앞에서 감소 구간이 적어도 하나 있었어야 하고, 이는 곧 극대점이 적어도 하나 있었어야 한다는 것과 동치이다. 따라서 입력&극대점 세는 과정을 마친 직후, 만약 단조증가 상태였고 지금까지 센 극대점 개수가 0이 아니라면 수열의 끝부분을 극대점으로 보고 cnt값을 1 증가시킨다.

 

극대점 개수를 구했으므로, 이제 `ceil(x/2)`연산을 반복해 주면 된다. cnt를 2로 나누기 위해 오른쪽으로 1비트 shift하고, cnt가 홀수이고 1이 아니었을 경우에만 1을 더해준다. 연산을 수행할 때마다 ans값을 1씩 증가시키고, cnt가 0이 되어 while문을 빠져나오면 ans를 출력하면 된다.

 

#include "bits/stdc++.h"
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, cnt = 0;
    cin >> n;
    vector<int> v(n);
    cin >> v[0];
    bool up = true;
    for(int i = 1; i < n; i++){
        cin >> v[i];
        if(v[i - 1] > v[i] && up){
            cnt++;
            up = false;
        }
        else if(v[i - 1] < v[i] && !up){
            up = true;
        }
    }
    if(cnt && up) cnt++;
    int ans = 0;
    while(cnt){
        cnt = (cnt >> 1) + ((cnt & 1) && (cnt != 1));
        ans++;
    }
    cout << ans;
}