5520번: The Clocks

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


$O(n*M*4^n)$ // n: 스위치 개수, M: 영향을 주는 시계의 최대 개수

모든 경우를 조사한다.

#include<cstdio>
const int f[][5] = { { 0,1,3,4 },{ 0,1,2 },{ 1,2,4,5 },{ 0,3,6 },{ 1,3,4,5,7 },{ 2,5,8 },{ 3,4,6,7 },{ 6,7,8 },{ 4,5,7,8 } }, c[] = { 4,3,4,3,5,3,4,3,4 };
int g[9], r = 1e9, p;
int main() {
    for (int i = 0; i < 9; i++) scanf("%d", g + i);
    for (int i = 1 << 18; i--;) {
        int t[9] = {}, s = 0, j;
        for (j = 0; j < 9; j++)
            for (int k = 0; k < c[j]; k++) t[f[j][k]] = (t[f[j][k]] + (i >> j * 2) * 3) % 4, s += (i >> j * 2) % 4;
        for (j = 0; j < 9; j++) if (g[j] ^ t[j]) break;
        if (j == 9 && r > s) r = s, p = i;
    }
    for (int i = 0; i < 9; i++) for (int k = (p >> i * 2) % 4; k--;) printf("%d ", i + 1);
    return 0;
}