백준 13413 오셀로 재배치

<링크>

https://www.acmicpc.net/problem/13413

<소스코드>

#include<stdio.h>
int main()
{
    char c1[100001], c2[100001];
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int N; scanf("%d", &N);
        scanf("%s", c1);
        scanf("%s", c2);
        int wbCnt=0, bwCnt = 0;
        for (int i = 0; i < N; ++i)
        {
            if (c1[i] == 'W' && c2[i] == 'B')
                ++wbCnt;
            else if (c1[i] == 'B' && c2[i] == 'W')
                ++bwCnt;
        }
        printf("%d\n", wbCnt < bwCnt ? bwCnt : wbCnt);
    }
}

<풀이>

백말(W)은 O, 흑말(B)는 X로 표시하면

OXOX

XOXO

이런식으로 되어있을 때, 즉

O      X

X 와  O  가 엇갈려있을 때 바꿔주면 된다.

따라서 

O

X

랑

X

O

의 개수를 각각 세어서 1번연산을 이용해 한쌍으로 매칭시켜주면 된다.

그 후 다 매칭시키고 나서 더이상 짝지어줄 수 있는 애들이 없으면 그냥 2번 연산을 이용해 바꾼다.

ex)

OXOOXX

XOXOOO

굵은애들은 윗라인 애들을 1번연산으로 맞바꿔주면 된다.

빨간애는 남은 나가리인데 걔는 2번연산으로 바꿔주면된다.