[성실코딩 2일차] 백준 #1018 체스판 다시 칠하기

문제 풀이

하나하나 확인해가며 구현문제로 풀었다. 

힌트를 얻은 건 문제에서 "체스판의 색은 항상 두 가지가 가능한데, 하나는 왼쪽 위 코너가 흰색인 것, 검정색인 것 두가지이다" 라는 언급이다.

체스판을 가능한 8*8로 모두 자르고 각각 검정으로 시작할 때, 흰색으로 시작할 때를 계산해서 최소값을 구했다.

(문제에서 N,M은 50보다 작기때문에 가능한 체스판의 경우는 42(50-8)*42(50-8)이다.

그리고 체스판의 모든 칸을 비교하기 때문에 *8

위의 연산을 검정일 때, 흰색일 때 모두 확인하여야 하기 때문에 *2

전체 연산 횟수는 42*42*8*2 = 28224

따라서 시간 초과가 발생하지 않을 것이라고 예상하고 구현문제로 풀었다.)

구현

char 배열c에 B, W를 저장해두고 각 문자를 입력받은 체스판의 칸과 비교하며 

다시 칠해야하는 체스판의 갯수를 카운트했다.

이때 int b는 배열 c의 인덱스로 0,1,0,1,...반복되고 있다. -> c[(++b)%2] 로 접근하고 있음.

C++구현코드

#include < iostream >
#include < string >

using namespace std;

#define INF 987654321

// 입력 받는 값
int N, M;
int map[50][50];

// 연산에 사용
char c[2] = { 'B','W' };
int b = 0; // c의 index

// answer
int minCnt = INF; 

int main(void) {

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < M; j++) {
			map[i][j]=str[j];
		}
	}

	// 왼쪽 위 모서리 W부터 시작
	b = 0;
	int cnt = 0;
	for (int i = 0; i <= N - 8; i++) {
		for (int j = 0; j <= M - 8; j++) {
			for (int ic = 0; ic < 8; ic++) {
				for (int jc = 0; jc < 8; jc++) {
					if ( map[i+ic][j+jc] != c[(++b) % 2] ) {
						cnt++;
					}
				}
				b++;
			}
			if (cnt < minCnt) minCnt = cnt;
			cnt = 0; //초기화
		}
	}

	// 왼쪽 위 모서리 B부터 시작
	b = 1;
	cnt = 0;
	for (int i = 0; i <= N - 8; i++) {
		for (int j = 0; j <= M - 8; j++) {
			for (int ic = 0; ic < 8; ic++) {
				for (int jc = 0; jc < 8; jc++) {
					if (map[i+ic][j+jc] != c[(++b) % 2]) {
						cnt++;
					}
				}
				b++;
			}
			if (cnt < minCnt) minCnt = cnt;
			cnt = 0; //초기화
		}
	}

	cout << minCnt << endl;
	return 0;
}