[BOJ 13413, Python 3] 오셀로 재배치

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

13413번: 오셀로 재배치

방법

1. 배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다.
2. 말 1개를 들어 뒤집어 놓아 색상을 변경한다.

 

풀이

이 문제는 두 가지 경우로 나누어서 풀 수 있습니다.

1) W, B의 개수가 같을 때

2) W, B의 개수가 다를 때

 

 

1) W, B의 개수가 같을 때

방법 1로 하는 것이 최적의 방법입니다.

왜냐하면 색깔이 서로 다른 부분만 확인해서 위치만 바꾸어주면 되는데, 서로 다른 부분의 개수는 짝수 개이므로(W, B의 개수가 같은데 i위치에서 색깔이 서로 다르면 다른 곳에서도 색깔이 다른 곳이 존재하기 때문) 서로 다른 부분의 개수를 2로 나누어 주는 것이 최적해입니다.

 

 

2) W, B의 개수가 다를 때

일단 W, B의 개수가 서로 같게 만들도록 방법 2를 사용합니다. 이때 색상을 변경하는 곳은 목표 상태와 처음 상태에서 문자열이 다른 곳을 바꿔주는 것이 제일 좋겠네요.

그러면 이제 W, B의 개수가 같으면서 위치만 서로 다른 부분이 존재합니다. 이러면 1번 풀이로 풀 수 있게 됩니다.

 

 

코드

for _ in range(int(input())):
    n = int(input())
    a = input()
    b = input()
 
    black, white = [a.count('B'), b.count('B')], [a.count('W'), b.count('W')]
    diff = sum(1 for i in range(n) if a[i] != b[i])
 
    if black[0] == black[1]: print(diff // 2)
    else:
        val = abs(black[0] - black[1])
        print(val + (diff - val) // 2)