[hacker rank]

문제 링크

 

풀이

마방진을 알아야 풀 수 있는 문제입니다. 영어로 magic square입니다. 문제에선 3 x 3 마방진만 주어지는데요. 마방진은 가로, 세로, 대각선의 합이 모두 같습니다. 3 x 3에서는 그 합이 15입니다. 이미 문제에 하나가 주어져 있죠. 이걸 90도로 세 번 돌리고, 좌우/상하 대칭, 대각선 대칭해서 총 여덟 개의 경우의 수를 직접 구했습니다. 그러고 나서 주어지는 문제의 차이가 가장 적은 값을 찾으면 됩니다. 마방진이 무엇인지 알고 있었다면 빨리 풀 수 있는 문제입니다.

 

코드

#include <cstdio>
int abs(int v)
{
	return v < 0 ? -v : v;
}
int min(int a, int b)
{
	return a < b ? a : b;
}
int main()
{
	int input[3][3] = 
	{
		{9, 3, 3}, {3, 3, 2}, {1, 8, 1}
	};


	int magic[24][3] =
	{
		{8, 3, 4}, {1, 5, 9}, {6, 7, 2},
		{6, 1, 8}, {7, 5, 3}, {2, 9, 4},
		{2, 7, 6}, {9, 5, 1}, {4, 3, 8},
		{4, 9, 2}, {3, 5, 7}, {8, 1, 6},
		{4, 3, 8}, {9, 5, 1}, {2, 7, 6},
		{6, 7, 2}, {1, 5, 9}, {8, 3, 4},
		{2, 9, 4}, {7, 5, 3}, {6, 1, 8},
		{8, 1, 6}, {3, 5, 7}, {4, 9, 2}
	};
	int min_val = 30, sum = 0;
	for (int i = 0; i < 24; ++i)
	{
		for (int j = 0; j < 3; ++j)
			sum += abs(magic[i][j] - input[i % 3][j]);

		if (0 == (i + 1) % 3)
		{
			min_val = min(sum, min_val);
			sum = 0;
		}
	}
	printf("%d\n", min_val);
}