[Python/파이썬] 백준 13413번 오셀로 재배치

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

코드

for _ in range(int(input())):
    n = int(input())
    othello_1 = input()
    othello_2 = input()

    white = 0
    black = 0
    for i in range(n):
        if othello_1[i] != othello_2[i]:
            if othello_1[i] == 'W':
                white += 1
            else:
                black += 1
    print(max(white, black))

 

코드는 다음과 같은 단계로 동작한다.

 

1. 초기 상태와 목표 상태의 같은 위치에 있는 말들을 비교합니다.

2. 서로 다른 색상의 말들을 찾아 각 색상별로 개수를 센다:

  2-1) 초기 상태에서 흰색('W')인데 목표 상태에서는 다른 색인 경우 → white 카운트 증가

  2-2) 초기 상태에서 검은색('B')인데 목표 상태에서는 다른 색인 경우 → black 카운트 증가

3. white와 black 중 큰 값이 필요한 최소 연산 횟수이다.

 

이 때 두 값 중 큰 값이 최소 연산 횟수인 이유는 더 적은 개수를 가진 색은 더 많은 개수를 가진 색과 짝을 이루어 교체할 수 있기 때문이다. 예를 들어, 흰색이 3개, 검은색이 5개라면 흰색은 검은색 중 3개와 바꾸면 된다. 그리고 남은 검은색 2개만 뒤집어주면 된다.

그렇기 때문에 white와 black 중 큰 값이 최소 연산 횟수가 되는 것이다.