반응형
링크
https://www.acmicpc.net/problem/1018
풀이
8*8짜리 부분을 선택하고 체스판으로 만들면 되는 문제입니다.
n, m은 50이하이고 자른 체스판은 8*8이기 때문에 모든 수를 고려해도 50*50*8*8로 시간 초과가 나지 않습니다.
(모든 수를 고려하는 걸 Brute-force 알고리즘이라고 합니다.)
자른 다음 저 위 두 사진처럼 만들면서 count를 해주면 되는데, 한 경우는 다른 경우의 64-count가 나오기 때문에 하나만 고려해도 됩니다.
칠하는 경우는 64가 최대이고, 그걸 고려해서 최소 경우를 찾아주면 됩니다.
색을 칠하는 방법은 홀홀과 짝짝은 같은 색, 홀짝과 짝홀은 같은 색이라는 것을 이용해서
(r%2)^(c%2) 이렇게 xor을 해줬습니다.
코드
//1018_체스판 다시 칠하기
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, ans=100;
char map[51][51];
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i) { //맵 받음
scanf("\n");
for (int j = 0; j < m; ++j) {
scanf("%c", &map[i][j]);
}
}
for (int i = 0; i <= n - 8; ++i) { //맵 순회
for (int j = 0; j <= m - 8; ++j) {
int cnt = 0;
for (int r = i; r < i + 8; ++r) { //8*8 맵 받아옴
for (int c = j; c < j + 8; ++c) {
if ((r % 2) ^ (c % 2)) { //짝홀, 홀짝일 때
if (map[r][c] == 'W') cnt++; //'W'->'B'
}
else { //홀홀, 짝짝일 때
if (map[r][c] == 'B') cnt++; //'B'->'W'
}
}
}
ans = min(ans, cnt); //1
ans = min(ans, 64 - cnt); //2
}
}
printf("%d\n", ans);
return 0;
}
반응형
'PS > BOJ' 카테고리의 다른 글
[백준 BOJ] 1074 Z (0) | 2019.08.11 |
---|---|
[백준 BOJ] 1436 영화감독 숌 (0) | 2019.08.11 |
[백준 BOJ] 11365 !밀비 급일 (0) | 2019.08.10 |
[백준 BOJ] 1476 날짜 계산 (0) | 2019.08.10 |
[백준 BOJ] 5532 방학 숙제 (0) | 2018.12.02 |