시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 1395 | 781 | 553 | 52.667% |
1부터 N2까지의 수가 하나씩 채워져 있는 크기가 N×N인 배열이 있고, 이 배열의 모든 행, 열, 길이가 N인 대각선의 합이 모두 같을 때, 매직 스퀘어라고 한다.
크기가 3×3인 배열 A가 주어졌을 때, 이 배열을 매직 스퀘어로 변경하려고 한다. 한 칸에 있는 수 a를 b로 변경하는 비용은 |a - b| 이다. 예를 들어, 아래와 같은 경우를 살펴보자.
5 3 4 1 5 8 6 4 2
이 배열의 수를 아래와 같이 변경하면 매직 스퀘어가 되고, 비용은 |5 - 8| + |8 - 9| + |4 - 7| = 7 이다.
8 3 4 1 5 9 6 7 2
3×3 크기의 배열 A가 주어졌을 때, 이 배열을 매직 스퀘어로 변경하는 비용의 최솟값을 구해보자. 배열 A는 1부터 9까지의 수로만 채워져 있고, 매직 스퀘어로 변경한 배열도 1부터 9까지의 수로만 채워져 있어야 한다.
총 세 개의 줄에 걸쳐서 배열 A의 원소가 주어진다.
첫째 줄에 배열 A를 매직 스퀘어로 변경하는 비용의 최솟값을 출력한다.
4 9 2 3 5 7 8 1 5
1
가장 오른쪽 아랫칸의 수를 6으로 변경하면 매직 스퀘어가 되고, 비용은 |5 - 6| = 1이다.
4 8 2 4 5 7 6 1 6
4
4 9 2 3 5 7 8 1 6
으로 변경할 수 있고, 비용은 |8 - 9| + |4 - 3| + |6 - 8| = 4이다.