백준20192 순서 섞기

문제 링크

http://icpc.me/20192

문제 출처

2020 KOI 고등부 2번

사용 알고리즘

시간복잡도

$O(N)$

풀이

문제를 풀기 위한 몇 가지 관찰을 증명 없이 소개하겠습니다.

인접한 수가 서로 같다면, 두 수를 하나로 합쳐도 답이 변하지 않습니다.
배열의 각 원소의 정확한 값보다는 현재 원소와 이전 원소의 대소 관계가 중요합니다. 예를 들어 2 3 5 1 4와 1 2 3 1 2의 정답은 동일합니다.

두 가지 관찰을 합쳐보면, 인접한 원소는 std::unique를 이용해 제거하면 되고, 원소의 증가/감소 여부가 바뀌는 횟수에 따라 정답이 결정된다는 사실을 알 수 있습니다. 정확하게는, 원소의 증가/감소 여부가 바뀌는 횟수와 $A_1, A_2$ 의 대소 관계에 따라 정답이 결정됩니다.

증가/감소 여부가 $i-1$ 번 바뀌었고, $A_1 < A_2$ 일 때 최소 횟수를 $D(i, 0)$ 이라고 정의합시다.
비슷하게, 증가/감소 여부가 $i-1$ 번 바뀌었고, $A_1 > A_2$ 일 때 최소 횟수를 $D(i, 1)$ 이라고 합시다.
DP의 상태 전이는 그림을 몇 번 그려보면 알 수 있습니다.

$i$ 가 짝수인 경우: $D(i, 0) = D(i/2, 0) + 1, D(i, 1) = D(i/2, 1) + 1$
$i$ 가 홀수인 경우: $D(i, 0) = D(i, 1) = min(D((i+1)/2, 0), D((i+1)/2, 1)) + 1$

점화식은 $O(N)$ 에 계산할 수 있고, 수열의 증가/감소 변화 횟수도 $O(N)$ 에 구할 수 있으므로 $O(N)$ 에 문제를 해결할 수 있습니다.

전체 코드

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int n, a[303030];
int dp[303030][2];

void calc(){
    dp[1][0] = 0; dp[1][1] = 1;
    dp[2][0] = 1; dp[2][1] = 2;
    for(int i=3; i<303030; i++){
        if(i & 1) dp[i][0] = dp[i][1] = min(dp[(i+1)/2][0], dp[(i+1)/2][1]) + 1;
        else dp[i][0] = dp[(i+1)/2][0] + 1, dp[i][1] = dp[(i+1)/2][1] + 1;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; for(int i=1; i<=n; i++) cin >> a[i];
    n = unique(a+1, a+n+1) - a - 1;
    if(n == 1){ cout << 0; return 0; }

    int type = (a[1] < a[2] ? 0 : 1), cnt = 1, st = type;
    for(int i=3; i<=n; i++){
        if(a[i-1] < a[i] && type == 1) type = 0, cnt++;
        if(a[i-1] > a[i] && type == 0) type = 1, cnt++;
    }

    calc();
    cout << dp[cnt][st];
}