[Jungol] 정올 2501 모양 정돈

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1762&sca=50

Approach

정돈된 최종 모양은 총 6가지 입니다.　

order[] = [1 2 3] / [1 3 2] / [2 1 3] / [2 3 1] / [3 1 2] / [3 2 1] 

위의 경우 [동그라미, 네모, 세모]로 [3 2 1] 구성으로 모여있다고 볼 수 있습니다.

각각의 경우를 구성하기 위해 바꾸기 횟수를 구해보면 됩니다.

① 6가지 경우 중 order[]를 하나 정해놓고

② 해당 위치에 있는 다른 모양의 개수를 세어서 교환해야 하는 횟수를 계산

 

시뮬레이션

배치하고자하는 순서 order[] = [3 2 1]일 때,

arr[] = [1 3 3 2 1 1 3 2] → cnt[] = [3 2 3] 

brr[] = [3 3 3 2 2 1 1 1] ← 『3』이 3개 / 『2』가 2개 / 『1』이 3개

 

pos[i][j] = i 구역에 있는 j의 개수

 

그룹 1먼저 채워주고 그룹 2, 그룹 3을 생각해주는 것입니다.

if (1,2) - (2,1) ≥ 0 ? (1,2) + (1,3) + (1,2) - (2,1) + (3,2)

else (1,2) + (1,3) + (1,3) - (3,1) + (2,3)

 

① 그룹(1)에 있는 그룹(2)(3)에 속해야 하는 요소들의 개수 (그룹(2),(3)에 속한 그룹(1)요소의 개수와 같다)

    (ex 입력이 1 2 2 3 1 1 1이 주어지고 [1, 2, 3] 순서라면 2 + 1)

② 그룹 (2)에 있는 그룹 (3)요소의 개수, 그룹 (3)에 있는 그룹 (2) 요소의 개수

     둘 중 큰 것 1, 2를 더해주면 최소한으로 움직이는 횟수가 됩니다.

이를 아래와 같이 표현도 가능합니다.

 

---

#include <stdio.h>
#define LM 100005
 
inline int min(int x, int y) { return x < y ? x : y; }
int N, arr[LM], brr[LM], ans = LM * 2;
int cnt[4], order[4], check[4];
 
int calc() {
    int i, j, k = 0, pos[4][4] = { {0} }, cnt1 = 0, cnt2 = 0;
    for (i = 1; i <= 3; i++) {
        for (j = 0; j < cnt[order[i]]; j++) {
            brr[k++] = order[i];
        }
    }
 
    for (i = 0; i < N; i++) {
        pos[brr[i]][arr[i]]++;
    }
 
    for (i = 1; i < 3; i++) {
        for (j = i + 1; j <= 3; j++) {
            k = min(pos[i][j], pos[j][i]);
            cnt1 += k;
            cnt2 += pos[i][j] + pos[j][i] - (k * 2);
        }
    }
    return cnt1 + cnt2 / 3 * 2;
}
 
void DFS(int step) {
    if (step > 3) {
        ans = min(ans, calc());
        return;
    }
    for (int i = 1; i <= 3; i++) {
        if (check[i]) continue;
        check[i] = 1;
        order[step] = i;
        DFS(step + 1);
        check[i] = 0;
    }
}
 
int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
        cnt[arr[i]]++;
    }
 
 
    DFS(1);
    printf("%d\n", ans);
    return 0;
}