[algospot][CLOCKSYNC] Synchronizing Clocks

문제 : https://algospot.com/judge/problem/read/CLOCKSYNC

---

완전탐색으로 돌린다.

만약 하나의 스위치를 4번 돌리면 원래 상태와 같아진다.

따라서 하나의 스위치를 0~3번 돌리면서 탐색해나간다.

void solve(시계상태, 스위치 번호, 스위치 누른 횟수){
    for (현재 스위치 누른 횟수 = [0,4)) {
        solve(시계상태, 스위치 번호 + 1, 스위치 누른 횟수 + 현재 스위치 누른 횟수);
        스위치 한 번 눌렀을 때 시계상태 갱신.
    }
}

의사 코드로 짜면 위와 같다.

여기에 몇 가지 종료 조건과 정답 갱신하는 코드 추가해준다..

 

시간복잡도는 O(4^10). 10은 스위치 개수이다.

---

소스코드 : https://gist.github.com/fpdjsns/78c84f397632a716b5f5477ee4dafdf6