-
백준(BOJ) 매직 스퀘어로 변경하기알고리즘 풀이/백준(Boj) 2020. 1. 1. 16:43
문제 : 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
풀이 :
1. 가로 세로 3 3 은 편의를 위해 1차원 배열로 바꾸어 풀었다. 매직 스퀘어는 1~9가 중복되지 않은 숫자로
만 이루어져 있기 때문에 123456789 ~ 987654321까지 next_permutation을 이용해 하나하나 다 처리해주자
2. 행열과 대각선이 모두 같은 후보가 구해졌다면 차를 구해준다.
3, 차에 최소를 출력한다.
코드 ( C++ )
'알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글
백준(BOJ) 16964번 DFS 스페셜 (0) 2020.01.11 백준(BOJ) 16954번 움직이는 미로 탈출 (0) 2020.01.07 백준(BOJ) 17779번 게리맨더링2 (0) 2020.01.01 백준(BOJ) 16956번 늑대와 양 (0) 2019.12.29 백준(BOJ) 16959번 체스판 여행 1 (0) 2019.12.26