[13413번] 오셀로 재배치

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 시뮬레이션

2. 시뮬레이션에서 요구하는 조건 응용

우선 값들을 받아들이고,

arr1과 arr2를 비교하여 arr1을 기준으로 흰색이라 다른 개수 , 검정색이라 다른 개수를 카운트 해준다.

그리고 항상 흰색이 더 많다고 가정을 해주고

검정색이 0이 될 때 까지 흰색과 검정색을 하나씩 빼주며 cnt를 1씩 증가시킨다.

마지막으로 cnt에 흰색 남은 것들을 모두 더하게 되면 정답이 된다.

즉, 흰색과 검정색이 1이상이라면 서로 위치를 바꾸는 행위를 하면 되고, 흰색만 남아있을 때는 뒤집어 바꾸기를 해야한다.

소스 코드 : 

#include <iostream>
 
#define swap(a,b) {int t; t = a; a = b; b = t;}
 
using namespace std;
 
int main()
{
    int tCase;
    int n;
    char arr1[100001];
    char arr2[100001];
    int cnt = 0;
    int Wdiff = 0;
    int Bdiff = 0;
 
    cin >> tCase;
    
    for (int j = 0; j < tCase; j++)
    {
        cin >> n;
        cin >> arr1;
        cin >> arr2;
 
        for (int i = 0; i < n; i++)
        {
            if (arr1[i] != arr2[i])
                arr1[i] == 'W' ? Wdiff++ : Bdiff++;
        }
 
        if(Wdiff < Bdiff)
            swap(Wdiff, Bdiff);
 
 
            while(Bdiff != 0)
            {
                Wdiff--;
                Bdiff--;
                cnt++;
            }
 
            cnt += Wdiff;
 
        cout << cnt << endl;
        cnt = 0;
        Wdiff = 0;
        Bdiff = 0;
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>