[백준 20192] 순서섞기

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

완전히 관찰 문제이다. 관찰을 해야되는 요소가 그렇게 많지는 않지만, 생각보다 발상이 어려운 문제, 하지만 발상이 떠오른다면 풀이는 되게 간단하다.

1. 풀이

우리가 할 수 있는 행동은 앞에서 빼거나, 뒤에서 빼거나 둘중 하나를 할 수 있다. 이 행동을 통해서 배열을 최소한의 행동으로 단조 증가형태로 만들려면 배열의 값들을 어떤 규칙으로 관리를 해야된다는 사실을 알 수 있다.

 

기본적으로 우리는 \(2\)번째 예제를 보고 하나의 관찰을 할 수 있다. 배열이 ↗ ↘ (↗ : 증가하는 형태, ↘ : 감소하는 형태) 이런 형태면 \(1\)번만에 정렬이 가능하다는 점을 관찰할 수 있다. 직접해보면 알 수 있다.

 

그러면 ↗ ↘ = ↗, ↘↗ = ↘, 배열의 어떤 형태들이 이런식으로 생기면 다음번에 어떠한 형태로 바뀔 수 있다는 핵심적인 관찰을 할 수 있다.

 

그렇다면 배열이 ↗ ↘↗ ↘↗ ↘↗ ↘ 이 있으면 다음과 같은 형태로 변환이 계속 가능하다.

↗ ↘↗ ↘↗ ↘↗ ↘ = ↗ ↘↗ ↘ = ↗ ↘ = ↗

각 앞뒤에서 ↗ ↘ or ↘↗을 떼와 앞에 붙여줄 수 있다. 또한 위의 예제를 통해 최소횟수를 유추할 수 있다.

 

\(\frac{n}{2}\)씩 계속 줄어드므로 증가하는 형태(↗)와 감소하는 형태(↘)의 개수를 k라고 둘때 \(log_2 k\) 만에 정렬이 가능하다는 관찰을 할 수 있다.

다른 케이스로는 ↗ ↘↗ ↘↗ ↘↗ 이런 앞뒤가 둘다 증가하는 형태가 나올 수도 있는데 이것 또한

↗ ↘↗ ↘↗ ↘↗ = ↗ ↘↗ ↘ = ↗ ↘↗ = ↗

이런식으로 정렬을 할 수 있으며 최종적으로 \(log_2 k\)에 올림을 해주면 답이라는 사실을 알 수 있다.

 

막상 코드를 짜면 되게 짧게 나온다.

2. 소스코드

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int n; cin >> n;
    int top = 1;
    bool up = true;
    int ans = 1;
    for (int i = 0; i < n; i++) {
        int a; cin >> a;
        if (up) {
            if (top > a) {
                up = false;
                ans++;
            }
        }
        else {
            if (top < a) {
                up = true;
                ans++;
            }
        }
        top = a;
    }
 
    cout << ceil(log2(ans));
    return 0;
}