728x90
๐๋ฌธ์ ๋ณด๋ฌ๊ฐ๊ธฐ
๐ง๐ป๐ปํ์ด ๊ณผ์
- ๊ฐ๊ฐ Nํ M์ด ํฌ๊ธฐ์ ํฐ์์ผ๋ก ์์ํ๋ ๋ณด๋ํ๊ณผ ๊ฒ์์์ผ๋ก ์์ํ๋ ๋ณด๋ํ ๋ ๊ฐ์ 2์ฐจ์ ๋ฐฐ์ด์ ์ค๋นํฉ๋๋ค.
- ๋ค์ ๊ณผ์ ์ ํตํด, ๊ต์ฒดํด์ผ ํ๋ ํ์๋ฅผ ๋์ ํ์ฌ ์ ์ฅํด ๋๊ฐ๋๋ค.
- ๋ค์์ ์ฌ๋ฐ๋ฅธ ์ฒด์คํ์ ๋ฐฐ์ด์ผ ๊ฒฝ์ฐ๋ฅผ ๋ํ๋
๋๋ค.
- (ํ + ์ด)์ด ์ง์์ผ ๊ฒฝ์ฐ, ์์ ์๊น(1, 1)๊ณผ ๊ฐ์์ผ ํ๋ค.
- (ํ + ์ด)์ด ํ์์ผ ๊ฒฝ์ฐ, ์์ ์๊น(1, 1)๊ณผ ๋ฌ๋ผ์ผ ํ๋ค.
- ์ ๋ ๊ฐ์ง ์ค ํ๋์ ํด๋นํ์ง ์์ ๊ฒฝ์ฐ, ์๊น์ ๊ต์ฒดํด์ผ ํ๋ค.
- ๋ค์์ ์ฌ๋ฐ๋ฅธ ์ฒด์คํ์ ๋ฐฐ์ด์ผ ๊ฒฝ์ฐ๋ฅผ ๋ํ๋
๋๋ค.
- ํ๊ณผ ์ด์ ๊ฐ๊ฐ K๋ถํฐ ์์ํ์ฌ, ๊ฐ๊ฐ N, M๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ๋๊น์ง 2์ค for ๋ฌธ์ ๋๋ ค๊ฐ๋ฉฐ ๋ค์์ ํ์ธํฉ๋๋ค.
- K x K ํฌ๊ธฐ์ ๋ณด๋์์ ์๊น ๋ณ๊ฒฝ ํ์๋ฅผ ์ป๋ ๋ฐฉ๋ฒ์ ๐2์ฐจ์ ๋ฐฐ์ด์์ ๋์ ํฉ์ ์ป๋ ๋ฐฉ์๊ณผ ๊ฐ์ต๋๋ค.
- ํฐ์์ผ๋ก ์์ํ๋ ๋ณด๋ํ์์ ๊ตฌํ ํ์์ ๊ฒ์์์ผ๋ก ์์ํ๋ ๋ณด๋ํ์์ ๊ตฌํ ํ์ ์ค ์์ ๊ฒ์ ์ถ๋ ฅํ๋ฉด ๋ฉ๋๋ค.
โ๏ธ์์ค ์ฝ๋ ๋ฐ ๊ฒฐ๊ณผ
#include <iostream>
#include <vector>
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
using namespace std;
using Board = vector<vector<int>>;
const char WHITE_COLOR = 'W';
const char BLACK_COLOR = 'B';
bool ShouldChangeColor(const char startColor, const char inputColor, const int row, const int col)
{
bool isEven = (row + col) % 2 == 0;
// (ํ + ์ด)์ด ์ง์๋ผ๋ฉด, ์์ ์(1, 1)๊ณผ ๊ฐ์์ผ ์ฌ๋ฐ๋ฅธ ๋ณด๋ํ์ด ๋๋ค.
if (isEven && startColor == inputColor)
return false;
// (ํ + ์ด)์ด ํ์๋ผ๋ฉด, ์์ ์(1, 1)๊ณผ ๋ฌ๋ผ์ผ ์ฌ๋ฐ๋ฅธ ๋ณด๋ํ์ด ๋๋ค.
else if (!isEven && startColor != inputColor)
return false;
return true;
}
int main()
{
FAST_IO;
int N, M, K;
cin >> N >> M >> K;
Board whiteStartBoard(N + 1, vector<int>(M + 1));
Board blackStartBoard(N + 1, vector<int>(M + 1));
for (int row = 1; row <= N; row++)
{
for (int col = 1; col <= M; col++)
{
char color;
cin >> color;
bool isChangedInWhiteBoard = ShouldChangeColor(WHITE_COLOR, color, row, col);
bool isChangedInBlackBoard = ShouldChangeColor(BLACK_COLOR, color, row, col);
// ์ด์ ๋์ ํฉ + ์๋ก์ด ๊ฐ
whiteStartBoard[row][col] = whiteStartBoard[row - 1][col] + whiteStartBoard[row][col - 1] - whiteStartBoard[row - 1][col - 1] + isChangedInWhiteBoard;
blackStartBoard[row][col] = blackStartBoard[row - 1][col] + blackStartBoard[row][col - 1] - blackStartBoard[row - 1][col - 1] + isChangedInBlackBoard;
}
}
int answerInWhiteBoard = 1000000000;
int answerInBlackBoard = 1000000000;
for (int row = K; row <= N; row++)
{
for (int col = K; col <= M; col++)
{
int minInWhiteBoard = whiteStartBoard[row][col] - whiteStartBoard[row - K][col] - whiteStartBoard[row][col - K] + whiteStartBoard[row - K][col - K];
int minInBlackBoard = blackStartBoard[row][col] - blackStartBoard[row - K][col] - blackStartBoard[row][col - K] + blackStartBoard[row - K][col - K];
answerInWhiteBoard = min(answerInWhiteBoard, minInWhiteBoard);
answerInBlackBoard = min(answerInBlackBoard, minInBlackBoard);
}
}
cout << min(answerInWhiteBoard, answerInBlackBoard);
return 0;
}
728x90
๋ฐ์ํ
'๐คAlgorithm > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] 2630๋ฒ | ์์ข ์ด ๋ง๋ค๊ธฐ (C++) (0) | 2023.08.31 |
---|---|
[BOJ] 11053๋ฒ | ๊ฐ์ฅ ๊ธด ์ฆ๊ฐํ๋ ๋ถ๋ถ ์์ด (C++) (0) | 2023.08.29 |
[BOJ] 11660๋ฒ | ๊ตฌ๊ฐ ํฉ ๊ตฌํ๊ธฐ 5 (C++) (0) | 2023.08.29 |
[BOJ] 2559๋ฒ | ์์ด (C++) (0) | 2023.08.27 |
[BOJ] 16139๋ฒ | ์ธ๊ฐ-์ปดํจํฐ ์ํธ์์ฉ (C++) (1) | 2023.08.27 |