[2016 국민대 교내 경시대회] A. 오셀로 재배치

BOJ 13413 오셀로 재배치 (https://www.acmicpc.net/problem/13413)

앞면은 검정, 뒷면은 흰색으로 된 오셀로 말을 

① 임의의 2개의 말을 위치를 바꾸거나(인접한 말일 필요없음)

② 말 1개를 뒤집어 색깔 변경

하는 작업 중 하나를 골라 시행할 수 있을 때, 초기 상태에서 목표 상태까지 도달할 수 있는 최소 작업 횟수를 구하는 문제입니다.

특정한 알고리즘을 사용하는 문제는 아니지만, 예시들을 통해 어떻게 말을 바꿔나가는 것이 최소 작업 횟수가 되는지를 생각하다 보면 방법을 알 수 있습니다.

제가 사용한 방법은 

B여야 하는데 W인 말과, W여야 하는데 B인 말을 서로 모두 바꾼 후에(①) 아직 목표 상태에 도달하지 못한 말들을 각각 뒤집는(②) 방법입니다.  검정색에서 흰색이 돼야 하는 말의 갯수를 n(B->W), 흰색에서 검정색이 돼야 하는 말의 갯수를 n(W->B) 라고 한다면, ①, ② 각각 작업 횟수는 

① min( n(B->W), n(W->B) )

② abs( n(B->W) - n(W->B) ) 

가 됩니다.

위의 상황을 그림으로 나타내면 다음과 같습니다.

그런데, n(B->W)가 n(W->B)보다 큰 경우에 ① = n(W->B), ② = n(B->W) - n(W->B)가 되어 ① + ②가 n(B->W)가 된다는 것을 계산을 통해 확인할 수 있습니다. 반대의 경우(n(W->B)가 n(B->W)보다 큰 경우)에 대해서도 계산해 보면, ① + ②가 n(B->W)와 n(W->B)의 값 중 큰 값이 이 된다는 것을 확인할 수 있습니다.

따라서,  ① + ②의 결과는 항상 

max( n(B->W), n(W->B) )

가 된다는 것을 알 수 있습니다. 

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <limits>
#include <math.h>
#include <stdlib.h>
 
using namespace std;
 
int main()
{
    int T; scanf("%d", &T);
 
    while(T--)
    {
        int len; scanf("%d", &len);
        string A,B; cin >> A >> B;
 
        int b=0, w=0;
 
        for(int i=0; i<len; i++)
        {
            if(A[i]=='B' && B[i]=='W') b++;
            if(A[i]=='W' && B[i]=='B') w++;
        }
 
        printf("%d\n", max(b,w));
    }
}