백준 1018 체스판 다시 칠하기

문제 링크: https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

가능한 모든 8 X 8 체스판마다 다시 칠해야 하는 정사각형의 갯수를 세고, 그중 최소값을 구하면 된다.

다시 칠해야 하는 정사각형 갯수의 최소값을 구할때, BWBWB...로 시작하는 보드와 WBWBW...로 시작하는 보드 둘다와 비교해봐야 한다.

아래는 위와 같이 구현하여 처음 AC를 받은 코드이다.

#include <bits/stdc++.h>
using namespace std;
 
int n, m;
char a[51][51];
 
int toPaint(int y, int x) {
    int ret = 1e9;
    int cnt = 0;
    for(int i = y; i < y + 8; i++) for(int j = x; j < x + 8; j++) {
        if((i + j) % 2 == 0 && a[i][j] == 'B') cnt++;
        if((i + j) % 2 != 0 && a[i][j] == 'W') cnt++;
    }
    ret = min(ret, cnt);
 
    cnt = 0;
    for(int i = y; i < y + 8; i++) for(int j = x; j < x + 8; j++) {
        if((i + j) % 2 == 0 && a[i][j] == 'W') cnt++;
        if((i + j) % 2 != 0 && a[i][j] == 'B') cnt++;
    }
    ret = min(ret, cnt);
 
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++)
        cin >> a[i][j];
 
    int ans = 1e9;
    for(int i = 0; i <= n - 8; i++) for(int j = 0; j <= m - 8; j++)
        ans = min(ans, toPaint(i, j));
 
    cout << ans << '\n';
    return 0;
}
 

위에서 BWBWB...로 시작하는 보드와 WBWBW...로 시작하는 보드 둘다와 비교해봐야 한다고 했는데, 사실상 이부분이 쓸데없이 코드를 길게만드는 부분이었다. BWBWB...로 시작하는 보드와 비교했을때 다시 칠해야 하는 정사각형 갯수가 x라고 하면, WBWBW...로 시작하는 보드와 비교했을때 다시 칠해야 하는 정사각형 갯수는 무조건 64 - x가 된다. 따라서 아래 코드와 같이 toPaint 함수의 길이를 짧게 고칠수 있다.

#include <bits/stdc++.h>
using namespace std;
 
int n, m;
char a[51][51];
 
int toPaint(int y, int x) {
    int ret = 1e9;
    int cnt = 0;
    for(int i = y; i < y + 8; i++) for(int j = x; j < x + 8; j++) {
        if((i + j) % 2 == 0 && a[i][j] == 'B') cnt++;
        if((i + j) % 2 != 0 && a[i][j] == 'W') cnt++;
    }
    return min({ret, cnt, 64 - cnt});
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++)
        cin >> a[i][j];
 
    int ans = 1e9;
    for(int i = 0; i <= n - 8; i++) for(int j = 0; j <= m - 8; j++)
        ans = min(ans, toPaint(i, j));
 
    cout << ans << '\n';
    return 0;
}