※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
이 문제를 풀 때, 가장 중요한 점은 "어떤 말을 어떤 말과 바꾸어서 배치를 해야 하는가" 가 아닙니다.
왜냐하면 우리는 몇 번째 말이 어디로 이동되어서 배치를 하는 것은 아무 것도 중요하지 않기 때문입니다.
첫 번째 말을 이동시키던, 세 번째 말을 이동시키던 이동하는 횟수만 최소화 하면 되는 것입니다.
따라서 이동 횟수를 최소화 하기 위해서는 1번째 방법(임의의 말을 골라 서로를 바꾼다)을 최대화 하는 것이 정답임을 직감해야합니다.
배치가 제대로 되지 않은 위치의 돌의 개수를 세어 봅시다. 이 때 흰색이 W, 검은색이 b라면 우리는 w, b 중 작은 값만큼의 횟수를 서로 바꾸어주고, 남은 돌을 반대로 뒤집어주면 되는 것이 최소임을 알 수 있습니다.
즉, $answer = w + b - min(w,b)$ 가 성립하게 됩니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
int tc;
cin >> tc;
while (tc--)
{
int l;
string s, t;
cin >> l >> s >> t;
int w = 0, b = 0;
for (int i = 0; i < s.length(); i++)
{
if (s[i] != t[i])
s[i] == 'W' ? w++ : b++;
}
cout << (w + b) - min(w, b) << "\n";
}
}