브루트포스 168p clocksync

algospot.com/judge/problem/read/CLOCKSYNC

algospot.com :: CLOCKSYNC

먼저 규칙을 찾았었다. 어떤 스위치를 누르면 어떻게 되는지 좀 알아보다가 

스위치는 10개 각각 4번씩 누르면 모든 경우의 수를 알 수 있는 문제였다. 그래서 계산을 해보니깐 시간적 여유가 있어서 그냥 브루트포스로 풀었다. 

 

4^10 의 시간복잡도 사실 이것보다 더 오래걸릴것이다. 재귀로 구성했고, 각 재귀함수 호출마다 반복문도 들어간다. 

 

그냥 단순하게 하나씩 눌러보자 => 이게 문제이다. 

 

#include<iostream>
#include<vector>
using namespace std;

int status[16];
vector<int> v[10] = { {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 solve(int idx, int num) {
	if (idx == 10) {
		for (int i = 0; i < 16; i++) {
			if (status[i] != 0) {
				return 987654321;
			}
		}
		return num;
	}
	
	int ans = 987654321;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < v[idx].size(); j++) {
			int a = v[idx][j];
			status[a] = (status[a] + i) % 4;
		}

		int cnt = solve(idx + 1, num + i);
		if (ans > cnt)ans = cnt;

		for (int j = 0; j < v[idx].size(); j++) {
			int a = v[idx][j];
	
			status[a] = ((status[a]-i)+4)%4;
			
		}

	}
	return ans;
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		for (int i = 0; i < 16; i++) {
			int a;
			cin >> a;
			a %= 12;
			a /= 3;
			status[i] = a;
		}
		int ans = solve(0, 0);
		if (ans == 987654321)cout << -1 << '\n';
		else cout << ans << '\n';
	}

}