백준(BOJ) 매직 스퀘어로 변경하기

문제 : https://www.acmicpc.net/problem/16945

16945번: 매직 스퀘어로 변경하기

 

풀이 :

1. 가로 세로 3 3 은 편의를 위해 1차원 배열로 바꾸어 풀었다. 매직 스퀘어는 1~9가 중복되지 않은 숫자로

만 이루어져 있기 때문에 123456789 ~ 987654321까지 next_permutation을 이용해 하나하나 다 처리해주자

 

2. 행열과 대각선이 모두 같은 후보가 구해졌다면 차를 구해준다. 

 

3, 차에 최소를 출력한다.

 

코드 ( C++ )

	#include <iostream>
	#include <algorithm>
	#include <vector>
	using namespace std;
	bool solve(vector<int> p)
	{
	//행열이 모두 같아야 한다
	int sum = p[0] + p[1] + p[2];
	if (sum != (p[3] + p[4] + p[5])) return false;
	if (sum != (p[6] + p[7] + p[8])) return false;
	// 열
	if (sum != (p[0] + p[3] + p[6])) return false;
	if (sum != (p[1] + p[4] + p[7])) return false;
	if (sum != (p[2] + p[5] + p[8])) return false;
	if (sum != (p[0] + p[4] + p[8])) return false;
	if (sum != (p[2] + p[4] + p[6])) return false;
	return true;
	}
	int main()
	{
	vector<int> a(9);
	for (int i = 0; i < 9; ++i)
	cin >> a[i];
	vector<int> picked(9);
	for (int i = 0; i < 9; ++i)
	picked[i] = i + 1;
	int ans = -1;
	do {
	if (solve(picked)) {
	int diff = 0;
	for (int i = 0; i < 9; ++i) {
	diff += abs(a[i] - picked[i]);
	}
	if (ans == -1 || ans > diff) {
	ans = diff;
	}
	}
	} while (next_permutation(picked.begin(), picked.end()));
	cout << ans << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub