매직 스퀘어로 변경하기
-
백준 16945번 매직 스퀘어로 변경하기PS 2020. 3. 17. 19:41
https://www.acmicpc.net/problem/16945 16945번: 매직 스퀘어로 변경하기 1부터 N2까지의 수가 하나씩 채워져 있는 크기가 N×N인 배열이 있고, 이 배열의 모든 행, 열, 길이가 N인 대각선의 합이 모두 같을 때, 매직 스퀘어라고 한다. 크기가 3×3인 배열 A가 주어졌을 때, 이 배열을 매직 스퀘어로 변경하려고 한다. 한 칸에 있는 수 a를 b로 변경하는 비용은 |a - b| 이다. 예를 들어, 아래와 같은 경우를 살펴보자. 5 3 4 1 5 8 6 4 2 이 배열의 수를 아래와 같이 변경하면 매직 스퀘어가 되고, 비용은 www.acmicpc.net n이 매우 작으므로 완전 탐색으로 풀 수 있습니다. 순열로 사각형을 만들어서 가중치를 계산하고 최솟값을 저장해나갑니다. ..