알고스팟 _ 시계 맞추기

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

algospot.com :: CLOCKSYNC

 풀이방법 

 주어진 시간은 10초 (약 10억개 연산)이다.

 이때 완전탐색으로 풀수 있는지 확인하려면 주의해야할 사항이 몇가지 있다.

 

 1. 스위치를 한번 누르면 3시간 ( 90도 )

 2. 스위치의 순서는 답에 지장이 없다. ( 조합문제임 )

 

 이때 1번을 생각해보면 4번누르면 360도 == 0도 이므로 안누른거나 진배없다. 그러면 스위치 한개당 4가지 ( 0번, 1번, 2번, 3번 )의 방법이 있다. 

 

 이제 시간을 구해보자!

 테스트 케이스 개수 x 4^ (스위치의 개수 10) 하면  31,457,280이므로 시간은 남아돈다. 

 그러니 완전탐색으로 풀도록 하자.

 

 푸는 방법은 별거없고 for문 (0 ~ 3)을 10번돌려 풀어도 되지만 그건 너무 힘드므로 재귀를 이용해서 풀면된다.

---

 전체코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;

// 0~ 15
int clockSynchronize[17];
vector<vector<int>> SwitchOfClock = { {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} };

bool isSucess()
{
	for (int i = 0; i < 16; i++)
		if (clockSynchronize[i] % 12 != 0)
			return false;
	return true;
}

void setTime(int selectSw, int time, bool isAdd)
{
	for (auto& ele : SwitchOfClock[selectSw])
	{
		if(isAdd == true)
			clockSynchronize[ele] += (time * 3);
		else
			clockSynchronize[ele] -= (time * 3);
	}
}

int getSucessSwitchCnt(int selectSw, int cnt)
{
	//탈출조건
	if (isSucess())
		return cnt;
	if (selectSw > 9)
		return INT_MAX;

	int ret = INT_MAX;
	for (int i = 0; i < 4; i++)
	{
		//여기서 time 추가
		setTime(selectSw, i, true);
		ret = min(ret, getSucessSwitchCnt(selectSw + 1, cnt + i));
		//여기서 추가했던 time값 회수
		setTime(selectSw, i, false);
	}
	return ret;
}

int main()
{
	int c;
	cin >> c;
	for (int t = 0; t < c; t++)
	{
		int value;
		for (int i = 0; i < 16; i++)
		{
			cin >> value;
			clockSynchronize[i] = value;
		}

		//get switchcnt
		int ans = getSucessSwitchCnt(0, 0);
		if (ans == INT_MAX)
			cout << -1 << endl;
		else
			cout << ans << endl;
	}
	return 0;
}

---

 후기

 이제 완전탐색 끝냈다!! ㅎㅎ