6장 무식하게 풀기 3

6.8 문제: 시계 맞추기 (문제ID: CLOCKSYNC, 난이도: 중)

문제 자세히 보기

#include <iostream>
#include <vector>

using namespace std;

int clocks[16];
vector<vector<int>> switches = {
    {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},
};

bool twelveAll() {
    for (int t : clocks)
        if (t % 4) return false;
    return true;
}

int on(int s) {
    if (s > 9) return 0;
    if (twelveAll()) return 0;
    int onOff = 0;

    for (int i = 0; i < 4; ++i) {
        onOff += on(s + 1);
        if (twelveAll()) return onOff + i;
        for (int c : switches[s])
            clocks[c]++;
    }

    return onOff;
}

int main() {
    ios_base::sync_with_stdio(false);
    int C;
    cin >> C;
    while (C--) {
        int t;
        for (int i = 0; i < 16; ++i) {
            cin >> t;
            clocks[i] = t / 3;
        }
        
        int output = on(0);
        if (twelveAll())
            cout << output << endl;
        else 
            cout << -1 << endl;
    }

    return 0;
}

Back to top ↑