[Hackerrank] Forming a Magic Square

문제

주어진 3*3 행렬은 1~9의 수를 가진다.

절댓값의 cost가 작은 수로 행렬의 수를 바꿀 수 있다. cost의 최솟값을 출력하자.

 

풀이

입력받은 행렬을 하나하나씩 비교하여 절댓값을 계산하려다가, magic matrix의 중간값은 5뿐이며, 절댓값이 최소가 되려면 (1,9),(2,8),(3,7),(4,6)의 조합을 중간의 5 주위로 배열해야한다는 것을 알았다.

홀수 조합이 첫째 줄에 오는 경우는 불가능하기 때문에 짝수 조합들이 첫째 줄에 오는 방향을 생각했고, 가능한 3*3 행렬은 8가지 경우 였다.

8가지 경우의 행렬을 제시하고 입력받은 행렬과 비교하여 가장 절댓값의 크기가 작은 수를 리턴한다.

 

코드

      

      

      

    
    

      <c++ />
    
int formingMagicSquare(int s_rows, int s_columns, int** s) {
    int magic_mat[8][3][3] = { // 가능한 magic matrix
    {{8, 1, 6}, {3, 5, 7}, {4, 9, 2}},
    {{6, 1, 8}, {7, 5, 3}, {2, 9, 4}},
    {{4, 9, 2}, {3, 5, 7}, {8, 1, 6}},
    {{2, 9, 4}, {7, 5, 3}, {6, 1, 8}}, 
    {{8, 3, 4}, {1, 5, 9}, {6, 7, 2}}, 
    {{4, 3, 8}, {9, 5, 1}, {2, 7, 6}}, 
    {{6, 7, 2}, {1, 5, 9}, {8, 3, 4}}, 
    {{2, 7, 6}, {9, 5, 1}, {4, 3, 8}},  
    };

    int A[3][3]; // 저장할 배열
    for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++)
        A[i][j] = s[i][j];
    }

    int min_cost = 81;
    for (int k = 0; k < 8; k++) { // 가능한 행렬과 비교
        int crt_cost = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++)
                crt_cost += abs( A[i][j] - magic_mat[k][i][j] ); // 절댓값을 비교하여 더함
        }
        if (crt_cost < min_cost) // cost가 가장 작은 수 저장
            min_cost = crt_cost;
    }
    return min_cost;
}

 

결과