1018번: 체스판 다시 칠하기 (acmicpc.net)
올바른 체크판이 될 수 있는 경우는
10101010
01010101
10101010
01010101
10101010
01010101
10101010
01010101
01010101
10101010
01010101
10101010
01010101
10101010
01010101
10101010
(흰색이 0, 흑색이 1)
이 두 가지밖에 없기 때문에, 처음에는 입력받은 보드를 순회하면서 8*8 체크보드를 만들 수 있는 모든 경우에 대해, top-left 칸이 어떤 색인지에 따라서 정답보드 1(top-left가 백),정답보드 2(top-left가 흑)와 비교하여 최소값을 업데이트했다.
그런데 틀려서, 예시 답안을 보면서 가만 다시 생각해 보니
1. 첫 번째 칸을 지금 이대로 놔두고 색칠하는 경우
2. 첫 번째 칸을 지금과 다르게 색칠하는 경우
이 두 가지 경우를 모두 고려해야 했다. 즉 top-left 칸의 색을 구별할 필요가 없이, 정답보드 1, 정답보드 2와 모두 비교하는 문제였다.
정답코드 첨부하고 마친다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minPaint = 100;
vector<vector<int>> answerBoard_1 = {
{1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}};
vector<vector<int>> answerBoard_2 = {
{0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 1}, {1, 0, 1, 0, 1, 0, 1, 0}};
void checkBoard(int initRow, int initCol, vector<vector<int>> &inputBoard, vector<vector<int>> &answerBoard)
{
int paintCnt = 0;
/* cout << "check will be ended at " << initRow + 8 << " " << initCol + 8 << endl; */
for (int i = initRow; i < initRow + 8; i++)
{
for (int j = initCol; j < initCol + 8; j++)
{
if (inputBoard[i][j] != answerBoard[i - initRow][j - initCol])
{
paintCnt++;
}
}
}
minPaint = min(minPaint, paintCnt);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int M;
int N;
cin >> M;
cin >> N;
vector<vector<int>> inputBoard(M, vector<int>(N));
// white = 0, black = 1
string boardInput;
for (int i = 0; i < M; i++)
{
cin >> boardInput;
for (int j = 0; j < N; j++)
{
if (boardInput.at(j) == 'W')
{
inputBoard[i][j] = 0;
}
else if (boardInput.at(j) == 'B')
{
inputBoard[i][j] = 1;
}
}
}
for (int i = 0; i < M - 7; i++)
{
for (int j = 0; j < N - 7; j++)
{
checkBoard(i, j, inputBoard, answerBoard_1);
checkBoard(i, j, inputBoard, answerBoard_2);
}
}
cout << minPaint;
}
'프로그래밍 > 백준 복기' 카테고리의 다른 글
[Greedy] 백준 2839: 설탕 배달 (2) | 2023.11.20 |
---|---|
[BruteForce] BOJ1436: 영화감독 숌 (1) | 2023.11.15 |
[BruteForce] 백준 15652: N과 M(4) (0) | 2022.10.06 |
[BruteForce] 백준 1748: 수 이어 쓰기 1 (0) | 2022.10.04 |
[BruteForce] 백준 1107: 리모컨 (2) | 2022.10.03 |