CLOCKSYNC

문제 링크

CLOCKSYNC

문제 풀이

스위치를 누를때마다 3시간씩 움직이기 때문에 4번을 누르게 되면 자기 자신으로 돌아온다. 따라서 0~3번만 누르는 경우만 확인하면 되므로 완전 탐색으로 모든 경우를 만들어 확인해본다.

구현

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

const int SWITCHS = 10, CLOCKS = 16, INF = 987654321;
int TC, clockSync[CLOCKS];
const char clockSwitch[SWITCHS][CLOCKS + 1] = {
    "xxx.............",
    "...x...x.x.x....",
    "....x.....x...xx",
    "x...xxxx........",
    "......xxx.x.x...",
    "x.x...........xx",
    "...x..........xx",
    "....xx.x......xx",
    ".xxxxx..........",
    "...xxx...x...x.."
};

int solve(int index) {
    if (index == SWITCHS) {
        for (int i = 0; i < CLOCKS; ++i)
            if (clockSync[i] != 12) return INF;
        return 0;
    }
    int ret = INF;
    for (int i = 0; i < 4; ++i) {
        ret = min(ret, i + solve(index + 1));
        for (int j = 0; j < CLOCKS; ++j) {
            if (clockSwitch[index][j] == 'x') {
                clockSync[j] += 3;
                if (clockSync[j] == 15) clockSync[j] = 3;
            }
        }
    }
    return ret;
}

int main() {
    cin >> TC;
    while (TC--) {
        for (int i = 0; i < CLOCKS; ++i)
            cin >> clockSync[i];
        int ret = solve(0);
        if (ret < INF) cout << ret << "\n";
        else cout << -1 << "\n";
    }
    return 0;
}