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

백준 13413 - 오셀로 재배치

시간 제한 2초, 메모리 제한 256MB

# 조건

• 로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다.
• 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다.
• 오셀로 말은 앞면이 검정, 뒷면이 흰색으로 된 말이다.
• 세희의 목표는 로봇을 이용하여 처음 배치된 오셀로 말을 주어진 형태로 바꾸는 일을 하는 것이다.
• 아래의 예시를 참고하자.

초기 상태	목표 상태
○●●○○	○●○●○

• 세희는 로봇을 이용해 2가지 작업 중 하나를 골라 진행할 수 있다.
  1. 배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다.
  2. 말 1개를 들어 뒤집어 놓아 색상을 변경한다.
• 위의 예시에서, 3번째와 4번째 말을 2번 작업을 통해 각각 뒤집으면 2번의 작업으로 목표 상태를 만들 수 있다.
• 하지만 1번 작업을 통해 3번째와 4번째 말을 골라 서로의 위치를 바꾸어주면 1번 만에 목표 상태에 도달할 수 있다.
• 초기 상태의 말과 목표 상태의 말이 주어질 때, 목표 상태에 도달할 수 있는 최소 횟수를 구하는 프로그램을 작성하시오.

입력

• 입력 데이터는 표준 입력을 사용한다.
• 입력은 T개의 테스트 데이터로 구성된다.
• 각 입력의 첫 번째 줄에는 오셀로 말의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.
• 각 입력의 두 번째 줄과 세 번째 줄에는 각각 오셀로 말의 초기 상태와 목표 상태가 주어진다.
• 초기 상태와 목표 상태의 말의 개수는 항상 N과 일치한다.
• 흰색 면이 보이는 경우에는 W, 검은색 면이 보이는 경우에는 B로 주어진다.

출력

• 출력은 표준 출력을 사용한다.
• 입력받은 데이터에 대해, 한 줄에 1개씩 초기 상태에서 목표 상태를 만들기 위한 작업의 최소 횟수를 구한다.

# 접근 방법

• 그리디 적으로 접근해보았다.
• 1개의 돌을 뒤집는 경우에는 2번 행위를 하면 된다.
• 서로 다른 2개의 돌을 교환하면 되는 경우에는 1번 행동을 하면 된다.
  • 다만, 같은 돌 2개가 필요한 경우에는 교환이 의미가 없으므로 2번 행동을 2번해야 한다.
• 즉, 목표 상태로 만들기 위해 필요한 흰돌과 검은 돌의 개수를 세어주고, 둘 중 작은 값은 교환을 통해 해결 가능하다.
• 큰 값에서 작은 값을 뺀 값(교환으로 해결 안된 경우)는 뒤집어서 만들어야 하므로 결국은 큰 값을 출력하는 것과 동일하다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

T = int(input())  
for _ in range(T):  
    N = int(input())  
    words = input().strip()  
    target = input().strip()  
    cnt1 = 0  
    cnt2 = 0  
    for i in range(N):  
        if words[i] != target[i]:  
            if target[i] == 'W':  
                cnt1 += 1  
            else:  
                cnt2 += 1  
    print(max(cnt1, cnt2))