CLOCKSYNC (중하, p. 168)

문제#

어떻게 풀었나?#

동일 스위치를 4번이상 누르게 되는 경우, 한번도 누르지 않은 경우와 같으므로 각각의 스위치는 4번 이상 누르는 경우가 없다. 스위치를 누르는 순서와 상관없이 결과는 같기 때문에 순서는 중요하지 않다.

이 2가지만 생각할 수 있다면, 모든 스위치를 0~3번 눌러보는 모든 경우의 수는 $4^{10}$가지 존재 -> 따라서 완탐으로 풀면 된다.

책에는 난이도가 ‘중’으로 나와있지만, 중하 정도가 적당할 것 같다.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
vector<int> sw[10] = {
    {0,1,2},
    {3,7,9,11},
    {4,10,14,15},
    {0,4,5,6,7},
    {6,7,8,10,12},
    {0,2,14,15},
    {3,14,15},
    {4,5,7,14,15},
    {1,2,3,4,5},
    {3,4,5,9,13}
};
int ck[16];
int mn_ans;
const int INF = 0x3f3f3f3f;

inline void Rotate(int x, int n) {
    ck[x]+=3*n;
    if(ck[x]>12) ck[x]-=12;
}

inline void RevRotate(int x, int n) {
    ck[x]-=3*n;
    if(ck[x]<=0) ck[x]+=12;
}

void Dfs(int x, int ans) {
    if(x==10) {
        int cnt=0;
        for(int i=0; i<16; i++) {
            if(ck[i]==12) cnt++;
        }
        if(cnt==16) mn_ans = min(mn_ans, ans);
        return;
    }

    for(int i = 0; i < 4; i++) {
        if(i > 0) {
            for(int ck_no : sw[x]) {
                Rotate(ck_no, i);
            }
        }
        Dfs(x+1,ans+i);
        if(i > 0) {
            for(int ck_no : sw[x]) {
                RevRotate(ck_no, i);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        mn_ans = INF;
        for(int i=0; i<16; i++) cin >> ck[i];
        Dfs(0,0);
        if(mn_ans == INF) puts("-1");
        else printf("%d\n", mn_ans);
    }
    return 0;
}