백준 16945. 매직 스퀘어로 변경하기

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

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

 

처음에 1부터 9까지의 숫자가 하나씩 채워져 있다는 말을 제대로 못봐서 좀 해맸다.

 

1. 1부터 9까지의 숫자가 한숫자당 한번씩만 나타날수 있으므로

   {1,2,...,9}의 벡터를 만들고 next_permuation 함수로 돌리면 모든 경우의 수가 나온다.

 

2. 만들어진 새로운 스퀘어가 매직 스퀘어인지 체크하고 

 

3. 매직 스퀘어가 맞다면 원본 스퀘어와 만들어진 스퀘어의 각 인덱스별로 차이의 절댓값을 구해서 모두 더한다.

4. 차의 합이 최댓값이 되도록 갱신한다.

 

 

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

vector<int> square;
vector<int> temp = {1,2,3,4,5,6,7,8,9};
int ans = 99999999;

// 만들어진 스퀘어가 매직넘버인지 판별
bool IsMagicNumber()
{
    int num = temp[0] + temp[1] + temp[2];

    if(temp[3]+temp[4]+temp[5] != num) return false;
    if(temp[6]+temp[7]+temp[8] != num) return false;
    if(temp[0]+temp[3]+temp[6] != num) return false;
    if(temp[1]+temp[4]+temp[7] != num) return false;
    if(temp[2]+temp[5]+temp[8] != num) return false;
    if(temp[0]+temp[4]+temp[8] != num) return false;
    if(temp[2]+temp[4]+temp[6] != num) return false;

    return true;
}

// 만들어진 스퀘어와 원본 스퀘어와의 차
int Calculate()
{
    int sum = 0;
    for(int i = 0; i < 9; i++)
    {
        sum += abs(square[i] - temp[i]);
    }
    return sum;
}

int main()
{
    // inputs
    for(int i = 0; i < 9; i++)
    {
        int num;
        cin >> num;
        square.push_back(num);
    }

    do {
        if(IsMagicNumber())
            ans = min(ans, Calculate());

    } while(next_permutation(temp.begin(), temp.end()));

    cout << ans;

}