알고스팟 시계맞추기 Synchronizing Clocks

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

algospot.com :: CLOCKSYNC

 

 

 

<접근방법>

처음에는 하나의 스위치에 의해서만 돌아가는 시계를 찾은 다음

그것들을 조합하면 필연적인 상태가 있을거라고 생각했고

그것을 이용해서 풀려고 했습니다.

하지만 터무니 없는 접근이었습니다 헿

 

잘생각해보면 시계의 상태는 3, 6, 9, 12 밖에 없으므로 시계를 4번 이상 돌리는 순간

중복 상태를 체크하는 꼴이 됩니다.

즉 한 스위치를 0, 1, 2, 3번 돌리면 그 스위치가 만들 수 있는 출력은 다 나온 것이 됩니다.

또 각 시계가 서로 영향을 끼치지 않으므로 스위치를 누르는 순서 또한 상관이 없습니다.

그러므로 10개의 스위치를 (0, 1, 2, 3)번 돌렸을 때, 각각을 확인해주는 완전탐색문제라는 것을 알 수 있습니다.

 

 

 

 

---

 

 

 

<시간복잡도>

경우의 수 : 4^10

스위치 조합을 완료했을 때, 시뮬레이션 약 120

 

30 * 120 * 4^10 하면 시간 안에 들어가긴 하네요..

 

(이게 맞는 계산인지 모르겠습니다..  가르침 부탁드립니다!)

 

 

 

 

---

 

 

 

<코드>

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

int tc, res;
int ck[16];
int arr[10];
vector<int> sw[10];
vector<int> v;

void set();

void simul() {
	int tclock[16];
	int tmp = 0;

	//처음 시계상태 복사
	for (int i = 0; i < 16; i++) {
		tclock[i] = ck[i];
	}

	//10개의 스위치에 대해서 시뮬레이션 돌려보자
	for (int i = 0; i < v.size(); i++) {
		int sw_cnt = v[i];
		tmp += sw_cnt;

		//해당 스위치가 동작시키는 시계들을 sw_cnt번 돌려보자
		for (int z = 0; z < sw_cnt; z++) {
			for (int j = 0; j < sw[i].size(); j++) {
				int ck_num = sw[i][j];

				if (tclock[ck_num] == 12) {
					tclock[ck_num] = 3;
				}
				else {
					tclock[ck_num] += 3;
				}
			}
		}
	}

	//모든 시계를 확인해보자
	//모든 시계가 12시를 가리킨다면 res++을 하자
	for (int i = 0; i < 16; i++) {
		if (tclock[i] != 12) return;
	}

	res += tmp;
	return;
}

void dfs(int dep = 0) {
	if (dep == 10) {
		simul();
		return;
	}

	for (int i = 0; i < 4; i++) {
		v.push_back(i);
		dfs(dep + 1);
		v.pop_back();
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	set();
	cin >> tc;
	while (tc--) {
		res = 0;
		v.clear();

		for (int i = 0; i < 16; i++) {
			cin >> ck[i];
		}

		dfs();

		if (res == 0) {
			cout << -1 << '\n';
		}
		else {
			cout << res << '\n';
		}
	}

	return 0;
}

void set() {
	sw[0].push_back(0);
	sw[0].push_back(1);
	sw[0].push_back(2);

	sw[1].push_back(3);
	sw[1].push_back(7);
	sw[1].push_back(9);
	sw[1].push_back(11);

	sw[2].push_back(4);
	sw[2].push_back(10);
	sw[2].push_back(14);
	sw[2].push_back(15);

	sw[3].push_back(0);
	sw[3].push_back(4);
	sw[3].push_back(5);
	sw[3].push_back(6);
	sw[3].push_back(7);

	sw[4].push_back(6);
	sw[4].push_back(7);
	sw[4].push_back(8);
	sw[4].push_back(10);
	sw[4].push_back(12);

	sw[5].push_back(0);
	sw[5].push_back(2);
	sw[5].push_back(14);
	sw[5].push_back(15);

	sw[6].push_back(3);
	sw[6].push_back(14);
	sw[6].push_back(15);

	sw[7].push_back(4);
	sw[7].push_back(5);
	sw[7].push_back(7);
	sw[7].push_back(14);
	sw[7].push_back(15);

	sw[8].push_back(1);
	sw[8].push_back(2);
	sw[8].push_back(3);
	sw[8].push_back(4);
	sw[8].push_back(5);

	sw[9].push_back(3);
	sw[9].push_back(4);
	sw[9].push_back(5);
	sw[9].push_back(9);
	sw[9].push_back(13);

}

 

 

 

 

 

---

 

 

 

 

<느낀점>

완탐임을 알고있었음에도 방향을 잡지 못했다.

완탐으로 풀려면 어떻게 해야할까에 대한 감이 부족하다.

 

 

google88718171ab2cd781.html

0.00MB