[알고스팟] CLOCKSYNC

#include<stdio.h>
#include<string.h>
 
int clocks[16];
int cntNum[10];
const int swNum[10] = { 3,4,4,5,5,4,3,5,5,5 };
const int swch[10][5] = { {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 swCnt[10];
const int INF = 987654321;
int min;
 
int check()
{
    int clockTemp[16];
 
    memcpy(clockTemp, clocks, sizeof(clocks));
 
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < swNum[i]; j++)
        {
            clockTemp[swch[i][j]]+= cntNum[i];
        }
    }
 
    for (int i = 0; i < 16; i++)
    {
        if (clockTemp[i] % 4) return 0;
    }
    return 1;
}
 
int switchOn(int cnt,int now)
{
    if (cnt >= min) return 0;
 
    if (now == 10)
    {
        if (check())
        {
            min = min > cnt ? cnt : min;
            return 1;
        }
        
        return 0;
    }
 
    int res = 0;
 
    for (int i = 0; i < 4; i++)
    {
        cntNum[now] = i;
        res += switchOn(cnt + i, now + 1);
    }
    return res;
}
 
int CLOCKSYNC()
{
    int c;
    scanf("%d\n", &c);
 
    while (c--)
    {
        memset(swCnt, 0, sizeof(swCnt));
        min = INF;
 
        for (int i = 0; i < 16; i++)
        {
            scanf("%d \n", clocks + i);
            clocks[i] = (clocks[i] / 3) % 4;
        }
 
        if (switchOn(0,0))
        {
            printf("%d\n", min);
        }
        else
        {
            printf("%d\n", -1);
        }
    }
    return 0;
}

PLUS) 위의 코드는 900ms정도의 시간이 걸렸는데, 답을 보니 0ms의 시간이 걸린 코드가 있었습니다. 한번 이를 분석하겠습니다.

#include <stdio.h>
#include <limits.h>
 
int switches[10][6] = {
    { 0,1,2,-1, },
    { 3,7,9,11,-1, },
    { 4,10,14,15,-1, },
    { 0,4,5,6,7,-1, },
    { 6,7,8,10,12,-1, },
    { 0,2,14,15,-1, },
    { 3,14,15,-1,},
    { 4,5,7,14,15,-1, },
    { 1,2,3,4,5,-1, },
    { 3,4,5,9,13,-1, } };
 
int solve_clock_order[10] = {8,11,13,6,10,7,4,1,3,14};
int solve_switch_order[10] = {4,1,9,3,2,7,8,0,6,5};
 
int check_order[6] = {0,2,5,9,12,15};
int pairs[10] = {1,11,10,6,8,14,3,7,4,13};
int clocks[16];
 
int main()
{
    int c;
    scanf("%d", &c);
 
    for (int i = 0; i < c; i++)
    {
        for (int j = 0; j < 16; j++)
        {
            int tmp;
            scanf("%d", &tmp);
 
            switch (tmp)
            {
                case 12:
                    clocks[j] = 0;
                    break;
                case 3:
                    clocks[j] = 1;
                    break;
                case 6:
                    clocks[j] = 2;
                    break;
                case 9:
                    clocks[j] = 3;
                    break;
            }
        }
 
        int total_cnt = 0;
 
        for(int j = 0; j < 10; j++)
        {
            int cnt = (4 - clocks[solve_clock_order[j]])%4;
            for(int k = 0; switches[solve_switch_order[j]][k] != -1; k++)
            {
                clocks[switches[solve_switch_order[j]][k]] = (clocks[switches[solve_switch_order[j]][k]] + cnt) % 4;
            }
            total_cnt += cnt;
        }
 
        bool possible = true;
        for(int j = 0; j < 6; j++)
        {
            if(clocks[check_order[j]] != 0)
            {
                possible = false;
                break;
            }
        }
 
        if(possible)
        {
            printf("%d\n", total_cnt);
        }
        else
        {
            printf("-1\n");
        }
    }
}
 

위의 코드에서 핵심은 3가지 입니다. 바로

int solve_clock_order[10] = {8,11,13,6,10,7,4,1,3,14};

int solve_switch_order[10] = {4,1,9,3,2,7,8,0,6,5};

int check_order[6] = {0,2,5,9,12,15};

이 부분입니다. 우선, 스위치를 확인해봅시다.

int switches[10][6] = {

    { 0,1,2,-1, },

    { 3,7,9,11,-1, },

    { 4,10,14,15,-1, },

    { 0,4,5,6,7,-1, },

    { 6,7,8,10,12,-1, },

    { 0,2,14,15,-1, },

    { 3,14,15,-1,},

    { 4,5,7,14,15,-1, },

    { 1,2,3,4,5,-1, },

    { 3,4,5,9,13,-1, } };

우선, 스위치 10개 중에서 딱 한번 등장하는 시계를 봅시다. 바로 4번 스위치의 8, 2번 스위치의 11, 5번 스위치의 13이다.

한 마디로, 8번 시계가 3시라면 4번 스위치를 3번 클릭하는 방법만이 8번 시계를 12시로 만들 수 있는 것입니다.

이런식으로 시계의 시간에 따라서 누를 수 밖에 없는 스위치들을 찾아 순서를 정하면, 위의 solve_siwtch_order 가 됩니다.

그 스위치와 연관되는 시계의 번호는 solve_clock_order가 됩니다.

스위치가 10개이고, 시계가 16개 이므로 모든 스위치를 눌러본 다음에 나머지 6개의 시계에 대해서는 답이 맞는지 확인을 해야합니다.

그 6개의 시계가 바로 check_order인 것입니다.

만약, 확인하는 시계들이 12시가 안된다면, 결국 저 스위치들을 눌러야하는데 그러면 결국 시계의 시간들이 다시 꼬여버리는 결과가 됩니다.

따라서, 10개의 스위치를 누른 다음에 나머지 6개의 시계가 12시를 가르키지 않는다면 결국 모든 시계를 12시로 만드는 방법이 없다는 것이고, -1을 출력하는 것입니다!