๋ณธ๋ฌธ์œผ๋กœ ๋ฐ”๋กœ๊ฐ€๊ธฐ
728x90
๐Ÿ”—๋ฌธ์ œ ๋ณด๋Ÿฌ๊ฐ€๊ธฐ
 

25682๋ฒˆ: ์ฒด์ŠคํŒ ๋‹ค์‹œ ์น ํ•˜๊ธฐ 2

์ฒซ์งธ ์ค„์— ์ •์ˆ˜ N, M, K๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ๋ณด๋“œ์˜ ๊ฐ ํ–‰์˜ ์ƒํƒœ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. B๋Š” ๊ฒ€์€์ƒ‰์ด๋ฉฐ, W๋Š” ํฐ์ƒ‰์ด๋‹ค.

www.acmicpc.net

 

๐Ÿง‘๐Ÿป‍๐Ÿ’ปํ’€์ด ๊ณผ์ •

  1. ๊ฐ๊ฐ Nํ–‰ M์—ด ํฌ๊ธฐ์˜ ํฐ์ƒ‰์œผ๋กœ ์‹œ์ž‘ํ•˜๋Š” ๋ณด๋“œํŒ๊ณผ ๊ฒ€์€์ƒ‰์œผ๋กœ ์‹œ์ž‘ํ•˜๋Š” ๋ณด๋“œํŒ ๋‘ ๊ฐœ์˜ 2์ฐจ์› ๋ฐฐ์—ด์„ ์ค€๋น„ํ•ฉ๋‹ˆ๋‹ค.
  2. ๋‹ค์Œ ๊ณผ์ •์„ ํ†ตํ•ด, ๊ต์ฒดํ•ด์•ผ ํ•˜๋Š” ํšŸ์ˆ˜๋ฅผ ๋ˆ„์ ํ•˜์—ฌ ์ €์žฅํ•ด ๋‚˜๊ฐ‘๋‹ˆ๋‹ค.
    • ๋‹ค์Œ์€ ์˜ฌ๋ฐ”๋ฅธ ์ฒด์ŠคํŒ์˜ ๋ฐฐ์—ด์ผ ๊ฒฝ์šฐ๋ฅผ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค.
      • (ํ–‰ + ์—ด)์ด ์ง์ˆ˜์ผ ๊ฒฝ์šฐ, ์‹œ์ž‘ ์ƒ‰๊น”(1, 1)๊ณผ ๊ฐ™์•„์•ผ ํ•œ๋‹ค.
      • (ํ–‰ + ์—ด)์ด ํ™€์ˆ˜์ผ ๊ฒฝ์šฐ, ์‹œ์ž‘ ์ƒ‰๊น”(1, 1)๊ณผ ๋‹ฌ๋ผ์•ผ ํ•œ๋‹ค.
      • ์œ„ ๋‘ ๊ฐ€์ง€ ์ค‘ ํ•˜๋‚˜์— ํ•ด๋‹นํ•˜์ง€ ์•Š์„ ๊ฒฝ์šฐ, ์ƒ‰๊น”์„ ๊ต์ฒดํ•ด์•ผ ํ•œ๋‹ค.
  3. ํ–‰๊ณผ ์—ด์„ ๊ฐ๊ฐ 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
๋ฐ˜์‘ํ˜•