CLOCKSYNC

#include <iostream>
#include <vector>

using namespace std;

const int MAX_BUFFER_SIZE = 1024;
const int SWITCH_NUM = 10;
const int CLOCK_NUM = 16;

const char* switches[10] = 
{
	{"oooxxxxxxxxxxxxx"},
	{"xxxoxxxoxoxoxxxx"},
	{"xxxxoxxxxxoxxxoo"},
	{"oxxxooooxxxxxxxx"},
	{"xxxxxxoooxoxoxxx"},
	{"oxoxxxxxxxxxxxoo"},
	{"xxxoxxxxxxxxxxoo"},
	{"xxxxooxoxxxxxxoo"},
	{"xoooooxxxxxxxxxx"},
	{"xxxoooxxxoxxxoxx"}
};
vector<int> clockState;
int pushed;

int getMinPush(int switchIdx);
void push(int switchIdx);
void unPushThreeTimes(int switchIdx);
bool IsSynced();
void splitStringWithDelim(char* source, vector<int> &result, char delim, int maxSize);

int main()
{
	int caseNum = 0;
	char inputBuffer[MAX_BUFFER_SIZE];

	cin >> caseNum;
	cin.ignore();

	for (int cIter = 0; cIter < caseNum; cIter++)
	{
		clockState.clear();
		pushed = 0;

		cin.getline(inputBuffer, MAX_BUFFER_SIZE);
		splitStringWithDelim(inputBuffer, clockState, ' ', MAX_BUFFER_SIZE);

		cout << getMinPush(0) << endl;
	}
}

int getMinPush(int switchIdx)
{
	int minPushed = 99999, ret = 0;

	// push 0 ~ 3 times
	for (int i = 0; i < 4; i++)
	{
		if(i != 0) push(switchIdx); 
		if (IsSynced()) return pushed;
		if (switchIdx != SWITCH_NUM - 1)
		{
			ret = getMinPush(switchIdx + 1);
			if (minPushed > ret) minPushed = ret;
		}
	}

	// restore clcokState
	unPushThreeTimes(switchIdx);

	// IF there's no answer, return INF
	if (switchIdx == SWITCH_NUM - 1) return 999999;

	return minPushed;
}

void push(int switchIdx)
{
	for (int i = 0; i < CLOCK_NUM; i++)
	{
		if (switches[switchIdx][i] == 'o')
		{
			clockState[i] = (clockState[i] + 3) % 12;
		}
	}

	pushed++;
}

void unPushThreeTimes(int switchIdx)
{
	for (int i = 0; i < CLOCK_NUM; i++)
	{
		if (switches[switchIdx][i] == 'o')
		{
			clockState[i] = (clockState[i] + 3) % 12;
		}
	}

	pushed -= 3;
}

bool IsSynced()
{
	for (int i = 0; i < CLOCK_NUM; i++)
	{
		if (clockState[i] % 12 != 0) return false;
	}

	return true;
}

void splitStringWithDelim(char* source, vector<int> &result, char delim, int maxSize)
{
	char *buf = new char[256]();
	int sourceIdx = 0;
	int bufIdx = 0;

	for (sourceIdx = 0; sourceIdx < maxSize; sourceIdx++)
	{
		if (source[sourceIdx] == delim || source[sourceIdx] == '\0')
		{
			// copy buffered string to result array
			buf[bufIdx] = '\0';
			result.push_back(atoi(buf));

			// if source string is end, break for loop
			if (source[sourceIdx] == '\0') break;

			bufIdx = 0;
		}
		else
		{
			buf[bufIdx] = source[sourceIdx];
			bufIdx++;
		}
	}

	return;
}

ClockSync 의 핵심은 스위치가 4번 눌리면 시계가 원상태로 돌아온다는 것이다. 즉, 4번 눌린 건 0번 눌린 것과 동일하다. 그래서 부분 문제의 수가 4^10 = 2^20 = (2^10)^2 = (10^3)^2 = 1000^2 = 1,000,000 으로 끝나는 것이다. 이 숫자는 (각 스위치의 버튼을 누르는 경우의 수) ^ (스위치의 총 갯수) 이다.

ClockSyncInput.txt

ClockSyncOutput.txt