[알고스팟] 시계 맞추기(C++)

문제 설명

https://www.algospot.com/judge/problem/read/CLOCKSYNC

algospot.com :: CLOCKSYNC

 

예제 입력

2
12 6 6 6 6 6 12 12 12 12 12 12 12 12 12 12
12 9 3 12 6 6 9 3 12 9 12 9 12 12 6 6

 

예제 출력

2
9

 

풀이

우선 스위치에 링크된 시계들을 다음과 같이 정의합니다.

vector<vector<int> > linkedClocks = {
        {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}
};

 

시계는 3시간씩 추가되기 때문에 4번 시계를 누르면 연결된 시계는 모두 12시간씩 앞으로 이동하므로 한번도 누르지 않은 것과 다름이 없게 됩니다. 따라서 10개의 스위치를 누르는 모든 경우의 수를 완전 탐색하여 가장 적게 누르는 횟수를 찾습니다. 

전체 경우의 수는 4^10(1,048,576)개가 됩니다.

int min_count = 987654321;
bool push(int num_switch){
    // 연결된 시계를 모두 3시간 씩 증가시킴
    for (int i = 0; i < linkedClocks[num_switch].size(); ++i){
        int num_clock = linkedClocks[num_switch][i];
        clockNumber[num_clock] = (clockNumber[num_clock] + 3) % 12 ;
    }
    // 시계가 모두 12시(0값)을 가리키고 있지 않은 경우 false 반환
    for (int i = 0; i < NUM_CLOCK; ++i){
        if(clockNumber[i] != 0)
            return false;
    }
    //시계가 모두 12시를 가리키고 있는 경우 true 반환
    return true;
}
void get_min_count(int start_pos, int push_count) {
    if(start_pos == NUM_SWITCH) return;
    // 스위치를 누르지 않고 재귀함수 호출
    get_min_count(start_pos+1, push_count);
    for(int i = 0; i < 4; ++i){
        push_count += 1;
        if(push(start_pos)) {
            //스위치 번호를 push 후 모두 12시를 가리키는 경우
            min_count = min(min_count, push_count);
        }
        // 스위치를 한 번 누르고 재귀함수 호출
        get_min_count(start_pos+1, push_count);
    }
}

 get_min_count() 함수는  start_pos(시작 스위치 번호)가0 부터 10이 될때까지 재귀함수가 호출됩니다.

push() 함수는 연결된 시계의 시간을 모두 3시간씩 증가시키고, 모두 12시를 가리키고 있는 경우 true를 반환합니다.

심플한 코드를 위해 12시는 0으로 표현하였습니다 (clockNumber[num_clock] = (clockNumber[num_clock] + 3) % 12)

 

 

전체 코드

#include <iostream>
#include <vector>

using namespace std;
const int NUM_CLOCK = 16;
const int NUM_SWITCH = 10;
int N;
vector<int> clockNumber(NUM_CLOCK, 0);
vector<vector<int> > linkedClocks = {
        {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 min_count = 987654321;
bool push(int num_switch){
    // 연결된 시계를 모두 3시간 씩 증가시킴
    for (int i = 0; i < linkedClocks[num_switch].size(); ++i){
        int num_clock = linkedClocks[num_switch][i];
        clockNumber[num_clock] = (clockNumber[num_clock] + 3) % 12 ;
    }
    // 시계가 모두 12시(0값)을 가리키고 있지 않은 경우 false 반환
    for (int i = 0; i < NUM_CLOCK; ++i){
        if(clockNumber[i] != 0)
            return false;
    }
    //시계가 모두 12시를 가리키고 있는 경우 true 반환
    return true;
}
void get_min_count(int start_pos, int push_count) {
    if(start_pos == NUM_SWITCH) return;
    // 스위치를 누르지 않고 재귀함수 호출
    get_min_count(start_pos+1, push_count);
    for(int i = 0; i < 4; ++i){
        push_count += 1;
        if(push(start_pos)) {
            //스위치 번호를 push 후 모두 12시를 가리키는 경우
            min_count = min(min_count, push_count);
        }
        // 스위치를 한 번 누르고 재귀함수 호출
        get_min_count(start_pos+1, push_count);
    }
}

int main() {
    cin >> N;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < NUM_CLOCK; ++j){
            cin >> clockNumber[j];
            if(clockNumber[j] == 12) clockNumber[j] = 0;
        }
        get_min_count(0, 0);
        if (min_count == 987654321)
            min_count = -1;
        cout << min_count << endl;
        min_count = 987654321;
    }
}