[C++] Algospot - 시계 맞추기(CLOCKSYNC)

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

algospot.com :: CLOCKSYNC

<풀이>

1. 16개 시계를 입력받는다.

2. 각 버튼을 0~3번씩 누르는 모든 경우를 시뮬레이션 해본다.

3. 가장 적게 버튼을 누른 횟수를 출력한다.

 

<해법>

1. 모든 경우를 다 해보는 방법

=> 모든 경우를 다 해야하므로 브루트 포스를 사용해야 합니다. 그 이후 어떤 방식을 다 해봐야 할지 고민해봐야 합니다. 곰곰히 생각해보면, 중요한 것은 버튼을 누르는 순서가 아닌 횟수라는 것을 알 수 있습니다. 그 횟수 또한 0에서 최대 3번까지로 제한된다는 것을 알 수 있습니다.

따라서, 각 버튼을 눌러야하는 횟수를 저장한 후 모든 경우를 시뮬레이션 해보는 방식으로 구현하였습니다.

 

#include <iostream>
#include <string>
#include <string.h>
 
using namespace std;
 
int clocks[16];
int playClocks[16];
string button[10] = {
    "xxx.............", //0번 버튼
    "...x...x.x.x....", //1번 버튼
    "....x.....x...xx", //2번 버튼
    "x...xxxx........", //...
    "......xxx.x.x...",
    "x.x...........xx",
    "...x..........xx",
    "....xx.x......xx",
    ".xxxxx..........",
    "...xxx...x...x.."
};
//0~9번 버튼을 몇 번 눌러야 하는지 저장하는 배열
int btnCnt[10];
int answer;
 
void makeClock(int index, int totalCount) {
 
    //정답보다 많은 스위치를 눌러야할 경우 -> 종료
    if (answer != -1 && answer <= totalCount) {
        return;
    }
 
    //종료 조건 : 10개의 버튼을 몇 번 눌러야할지 모두 정한 경우
    if (index == 10) {
 
        //시뮬레이션 위해 복사
        memcpy(playClocks, clocks, sizeof(playClocks));
 
        //시뮬레이션
        for (int i = 0; i < 10; i++) {
            int btn = i;
            int count = btnCnt[i];
 
            for (int j = 0; j < 16; j++) {
                if (button[btn][j] == 'x') {
                    playClocks[j] += 3 * count;
                }
            }
        }
 
        //모두 12시를 가르키는지 확인
        bool canAnswer = true;
        for (int i = 0; i < 16; i++) {
            if (playClocks[i] % 12 != 0) {
                canAnswer = false;
                break;
            }
        }
 
        //결과 갱신
        if (canAnswer) {
            if (answer == -1 || totalCount < answer) {
                answer = totalCount;
            }
        }
 
        return;
    }
 
    //0~3번 누르는 모든 경우 해보기
    for (int i = 0; i < 4; i++) {
        btnCnt[index] = i;
        makeClock(index + 1, totalCount + i);
    }
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        memset(clocks, 0, sizeof(clocks));
        memset(btnCnt, 0, sizeof(btnCnt));
        answer = -1;
 
        //입력
        for (int i = 0; i < 16; i++) {
            cin >> clocks[i];
        }
 
        //해법
        /*
        각 스위치마다 몇 번씩 눌러야 하는지 정하고,
        각 경우마다 모두 시뮬레이션
        */
        makeClock(0, 0);
 
        //출력
        cout << answer << "\n";
    }
 
    //종료
    return 0;
}

 

브루트포스, 구현, 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.