A번 문제: 최대 반복 수 유지하기

수열이 감소에서 증가로 변하는 경우, 중간에 연속된 동일한 값의 구간은 변경되지 않으며, 그 앞과 뒤는 반드시 변경되어야 한다. 왜냐하면 어떤 원소의 앞쪽 원소들은 기존에는 자신보다 크거나 같아야 했지만, 변화 후에는 작거나 같아야 하며, 뒤쪽 원소들 역시 반대로 작거나 같았던 것이 크거나 같아져야 하기 때문이다. 따라서 같은 값인 부분은 그대로 두고, 다른 값은 모두 바꿔야 한다. 이때 가장 많은 개수를 가진 값을 고정시키면 최소의 변환 횟수를 얻을 수 있다.

#include <bits/stdc++.h>

using namespace std;

int n;
int h[55];
int cnt[55];
int ans;

void solve() {
    memset(cnt, 0, sizeof(cnt));
    ans = 0;
    
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
        cnt[h[i]]++;
        if (cnt[h[i]] > ans) ans = cnt[h[i]];
    }
    
    cout << n - ans << '\n';
}

signed main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

B번 문제: 인접 교환 가능성 판단

각 숫자는 자신과 차이가 1인 인접한 위치의 숫자와만 교환 가능하다. 즉, 숫자 \(i\)는 \(i-1\) 또는 \(i+1\)과만 교환할 수 있으며, 최대 두 번의 교환으로 자신의 위치를 옮길 수 있다. 하지만 만약 현재 위치와 목표 위치 간 거리가 2 이상이라면, 두 번의 교환으로는 정렬을 완성할 수 없다. 왜냐하면 한 번의 교환으로는 최대 1칸 이동할 수 있고, 두 번의 교환 시에도 2칸 이내로만 이동 가능하기 때문이다.

#include <bits/stdc++.h>

using namespace std;

int n;
int pos[200005];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> pos[i];
    
    for (int i = 1; i <= n; ++i)
        if (abs(pos[i] - i) >= 2) {
            cout << "NO\n";
            return;
        }
    
    cout << "YES\n";
}

signed main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

C번 문제: 완전제곱수 간격 배열 구성

짝수 길이의 수열은 \(1,1,2,2,3,3,\dots\)와 같이 배치하면, 같은 숫자 사이의 간격이 1로 항상 완전제곱수(1²)가 된다. 홀수 길이의 경우, 3개의 동일한 수를 특정 위치에 배치해 완전제곱수 간격을 만족해야 한다. 예를 들어, 1, 10, 26번째 위치에 동일한 수를 넣으면, 1과 10 사이의 간격은 9(3²), 10과 26 사이의 간격은 16(4²), 1과 26 사이의 간격은 25(5²)로 모두 완전제곱수이다. 이후 남은 구간은 짝수 방식으로 채우면 된다. 단, 전체 길이가 27 미만일 경우 해가 존재하지 않는다.

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

int n;
int res[200005];

void solve() {
    cin >> n;
    
    if (n % 2 == 0) {
        for (int i = 1; i <= n; ++i)
            cout << (i + 1) / 2 << " ";
        cout << "\n";
    } else {
        if (n < 27) {
            cout << -1 << "\n";
            return;
        }
        
        memset(res, 0, sizeof(res));
        res[1] = res[10] = res[26] = 1;
        res[23] = res[27] = 2;
        
        int count = 3;
        bool flag = false;
        for (int i = 1; i <= n; ++i) {
            if (res[i]) continue;
            res[i] = count;
            flag = !flag;
            if (!flag) count++;
        }
        
        for (int i = 1; i <= n; ++i)
            cout << res[i] << " ";
        cout << "\n";
    }
}

signed main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

D번 문제: 역방향 그리디 탐색

최댓값 이후의 모든 원소는 최댓값까지 도달할 수 있다. 왜냐하면 최댓값 뒤의 원소들보다 큰 값이 있으면, 그 값은 최댓값 뒤의 최소값을 거쳐 최댓값으로 이동할 수 있기 때문이다. 이를 활용해, 값의 범위를 내림차순으로 탐색하면서, 각 값이 이전 최소값보다 크면 해당 최소값으로 먼저 이동한 후 최댓값으로 이동하며, 그렇지 않으면 해당 값부터 다음 최대값까지는 해당 값으로 고정한다.

#include <bits/stdc++.h>

using namespace std;

int n;
int a[500005];
int ans[500005];
map<int, int> first_occurrence;
int prefix_max[500005];

void solve() {
    first_occurrence.clear();
    scanf("%d", &n);
    
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        if (!first_occurrence[a[i]]) 
            first_occurrence[a[i]] = i;
        prefix_max[i] = max(prefix_max[i-1], a[i]);
    }
    
    int right_bound = n;
    int current_limit = n + 1;
    int invalid_pos = n + 1;
    
    for (int val = n; val >= 1; --val) {
        if (first_occurrence[val] == 0 || first_occurrence[val] > right_bound)
            continue;
            
        if (val <= current_limit) {
            current_limit = val;
            invalid_pos = prefix_max[first_occurrence[val]];
        }
        
        for (int j = first_occurrence[val]; j <= right_bound; ++j) {
            ans[j] = invalid_pos;
            current_limit = min(current_limit, a[j]);
        }
        right_bound = first_occurrence[val] - 1;
    }
    
    for (int i = 1; i <= n; ++i)
        printf("%d ", ans[i]);
    printf("\n");
}

signed main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}