[BOJ 2450 // C++] 모양 정돈

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2450번 문제인 모양 정돈이다.
문제는 아래 링크를 확인하자.

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

 

주어진 모양의 정렬 결과는 각 도형이 등장하는 순서의 경우의 수와 같은 6가지뿐임을 관찰하자.

따라서 결과로 나올 수 있는 6가지 배치 각각에 대하여 필요한 최소 맞바꾸기 횟수를 구하는 것으로 문제를 해결할 수 있다.

 

각 경우에 대한 최소 맞바꾸기 횟수는 permutation cycle decomposition 개념을 활용하면 어렵지 않게 구할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int P[3] = {0,1,2};
bool comp(int &x, int &y) {
    return P[x] < P[y];
}

int N, ans = 0x3f3f3f3f;
int A[100000], B[100000];
int cnt[3][3];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i], A[i]--;
    for (int i = 0; i < N; i++) B[i] = A[i];
    for (int k = 0; k < 6; k++) {
        sort(A, A + N, comp);
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < N; i++) {
            cnt[A[i]][B[i]]++;
        }
        int val1 = min(cnt[0][1], cnt[1][0]);
        cnt[0][1] -= val1, cnt[1][0] -= val1;
        int val2 = min(cnt[0][2], cnt[2][0]);
        cnt[0][2] -= val2, cnt[2][0] -= val2;
        int val3 = min(cnt[1][2], cnt[2][1]);
        cnt[1][2] -= val3, cnt[2][1] -= val3;
        ans = min(ans, val1 + val2 + val3 + (cnt[1][0] + cnt[0][1]) * 2);
        next_permutation(P, P + 3);
    }

    cout << ans;
}