[BOJ] 백준 1018 체스판 다시 칠하기 (Swift)

문제

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

1018번: 체스판 다시 칠하기

풀이

먼저, 보드를 8x8 사이즈로 잘라서 체스판을 만들 수 있는 경우를 다 따져봐야합니다.
예를 들어 9x9 사이즈라면, 총 4개의 체스판이 나올 수 있습니다.

자른 후에는 8x8 사이즈의 체스판을 맨 왼쪽 윗칸이 흰색인 체스판, 검은색인 체스판과 다르게 칠해져있는 경우의 수를 찾으면 됩니다.

맨 왼쪽 윗칸이 흰색인 체스판을 보면, 행과 열의 합이 짝수인 경우는 흰색으로, 홀수인 경우는 검은색으로 칠해져있습니다.
마찬가지로 맨 왼쪽 윗칸이 검은색인 체스판은 행과 열의 합이 짝수인 경우는 검은색, 홀수인 경우는 흰색입니다.

이 성질을 이용하여,
행과 열의 합이 짝수이고 흰색, 행과 열이 홀수이고 검은색인 체스판과 다른 갯수와
행과 열의 합이 짝수이고 검은색, 행과 열이 홀수이고 흰색인 체스판과 다른 갯수를 세어 더 적게 칠하는 경우를 계속해서 갱신해주면 됩니다.

n과 m이 최대 50이므로, 42 * 42 * 8 * 8 = 약 10만번의 연산을 통해 원하는 답을 구할 수 있습니다.

즉, 모든 경우의 수를 확인하는 완전탐색 알고리즘으로 풀이할 수 있습니다.

소스코드

후기

입력이 크지않아 완전탐색으로 풀 수 있는 문제입니다.
처음에 맨 왼쪽 윗칸이 검은색으로 시작하는 체스판, 흰색으로 시작하는 체스판을 초기화하고
자른 체스판과 비교하는 방법으로도 풀이할 수 있습니다.