백준 BOJ 5520 - The Clocks

https://www.acmicpc.net/problem/5520

5520번: The Clocks

스터디 하면서 풀어본 문제.

일단 제일 처음 든 생각은,

시계를 돌릴때 4번 돌리면 아무 의미가 없어진다는것

시계를 돌릴수 있는 9가지 방법이 주어지는데,

이 9가지 방법 각각을 4n+m번 돌린 경우는 m번 돌린 경우와 동일하다.

즉 한가지 방법당 0,1,2,3 번 돌리는 경우가 존재할 수 있으며,

이러한 방법이 9개이므로

 

전체 경우의 수를 브루트포싱하면

4^9 = 2^18 = 262144 이다.

충분히 시간복잡도 안에 해결할 수 있음을 알았으니

브루트포싱을 통해 시계를 돌리는 모든 경우의 수에 대해서

결과값이 0으로만 채워진 배열일때를 추려내고,

추려내진 경우들에 대해서

돌리는 횟수를 싹 다 더한 수가 최소가 되도록 선택해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;

int arr[3][3] = {0};
int cnt[10] = {0};

vector<int> dx[9];
vector<int> dy[9];

vector<int> ans;

int calc(){
	int copy[3][3] = {0};
	for(int i=0; i<3; i++) for(int j=0; j<3; j++) copy[i][j] = arr[i][j];
	
	for(int i=0; i<9; i++){
		for(int j=0; j<dx[i].size(); j++){
			copy[dx[i][j]][dy[i][j]] += cnt[i];
			copy[dx[i][j]][dy[i][j]] %= 4;
		}
	}
	
	int ans = 0;
	for(int i=0; i<3; i++) for(int j=0; j<3; j++) ans += copy[i][j];
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	dx[0] = {0,0,1,1};
	dy[0] = {0,1,0,1};
	
	dx[1] = {0,0,0};
	dy[1] = {0,1,2};
	
	dx[2] = {0,0,1,1};
	dy[2] = {1,2,1,2};
	
	dx[3] = {0,1,2};
	dy[3] = {0,0,0};
	
	dx[4] = {0,1,1,1,2};
	dy[4] = {1,0,1,2,1};
	
	dx[5] = {0,1,2};
	dy[5] = {2,2,2};
	
	dx[6] = {1,1,2,2};
	dy[6] = {0,1,0,1};
	
	dx[7] = {2,2,2};
	dy[7] = {0,1,2};
	
	dx[8] = {1,1,2,2};
	dy[8] = {1,2,1,2};
	
	for(int i=0; i<3; i++){
		for(int j=0; j<3; j++){
			cin >> arr[i][j];
		}
	}
	
	for(int i=0; i<262144; i++){
		int ptr = 0;
		int tmp = i;
		while(tmp){
			cnt[ptr++] = tmp%4;
			tmp/=4;
		}
		
		if(calc() == 0){
			int tmp = 0;
			for(int i=0; i<9; i++) tmp += cnt[i];
			
			if(ans.size() == 0 || ans.size() > tmp){
				ans.clear();
				for(int i=0; i<9; i++){
					for(int j=0; j<cnt[i]; j++){
						ans.push_back(i+1);
					}
				}
			}
		}
	}
	
	for(auto it : ans){
		cout << it << " ";
	}
	return 0;
}