CLOCKSYNC(C언어)

CLOCKSYNC

처음에는 CLOCK 값을 증가시키면서 , CLOCK을 12시에 맞추고 다음 CLOCK 으로 이동하고 이런 방식을 생각했었는데

이런식으로는 계속 문제가 꼬여가서 풀 수 없다고 생각해서 다시 생각해보았다.

BUTTON 중심으로 접근하다 보니, 0~9번 까지의 버튼을 몇번 누르는지에 대한 재귀 접근으로 풀 수 있었다.

그리고 가장 중요한 방법은 최소값을 구하는 것이고, 한 버튼을 0번 누르나 4번 누르나 똑같다는 점이었다.

따라서 최소값을 구하기 위해서는 버튼은 최대 3번까지만 누르는 방식으로 재귀함수 코드를 구현할 수 있었다.

또 모든 버튼을 3번씩 누르면 최대 3*16=48번의 버튼을 누를 수 있기 때문에, 기존의 ans 값을 50으로 설정하였다.

search_button 함수를 통해서 몇번 버튼을 몇번 누를 것인지를 정하고,

change_clock 함수를 통해서 그 버튼을 몇번 눌렀을 때, 시간을 변경해주는 방식으로 구현했다.

<정답 코드 - C>

#include<stdio.h>
#define clock_num 16
#define button_num 10
//버튼에 따른 연결된 스위치, 연결이 되지 않았으면 -1
const int button[button_num][5] = {
    {0,1,2,-1,-1},
    {3,7,9,11,-1},
    {4,10,14,15,-1},
    {0,4,5,6,7},
    {6,7,8,10,12},
    {0,2,14,15,-1},
    {3,14,15,-1,-1},
    {4,5,7,14,15},
    {1,2,3,4,5},
    {3,4,5,9,13}
};
 
void change_clock(int *clock, int button_index, int move_time);
void search_button(int *clock,int clock_index,int cnt,int *ans);
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc, t, i;
    int ans;
    int clock[16];
    scanf("%d", &tc);
    for (t = 1; t <= tc; t++) {
        
        ans = 50;
        for (i = 0; i < clock_num; i++) {
            scanf("%d", &clock[i]);
        }
 
        search_button(clock,0,0,&ans);
 
        //정답을 구할 수 없는 경우
        if (ans == 50)
            ans = -1;
 
        printf("%d\n", ans);
    }
 
    return 0;
}
 
//해당 버튼의 타이머들 변경하기
void change_clock(int *clock,int button_index,int move_time)
{
    int i, num;
 
    //버튼에 연결된 스위치 탐색
    for (i = 0; i < 5; i++) {
        //num 는 버튼에 연결되어 있는 스위치 인덱스
        num = button[button_index][i];
        if (num != -1) {
            //시계 값 변경
            clock[num] += move_time;
 
            if (clock[num] <= 0)
                clock[num] += 12;
 
            if (clock[num] > 12)
                clock[num] -= 12;
        }
    }
}
 
void search_button(int *clock,int button_index,int cnt,int *ans)
{
    int i,j;
 
    //기존의 정답보다 값이 클 때
    if (cnt >= *ans)
        return;
 
    //모든 버튼을 다 해봤을 때
    if (button_index == button_num)
    {
        for (j = 0; j < clock_num; j++)
        {
            if (clock[j] != 12)
                return;
        }
 
        if (*ans > cnt)
        {
            *ans = cnt;
        }
        return;
    }
 
    //버튼을 몇번누르는지
    for (i = 0; i < 4; i++) {
        //butto_index 번 버튼을 i번 눌렀을 경우
        change_clock(clock, button_index, 3 * i);
        search_button(clock, button_index + 1, cnt + i, ans);
        change_clock(clock, button_index, -3 * i);
    }
}