백준 13413

T = int(input())
for i in range(T):
    black = 0; white = 0
    n = int(input())
    first = list(input())
    second = list(input())
    for j in range(n):
        if first[j] != second[j]:
            if first[j] == 'B':
                black += 1
            else:
                white += 1
    print(max(black, white))

최소 작업의 횟수를 구해야 하므로 가능한 1번방법을 먼저 쓰고, 남은 말들을 2번방법으로 마무리 해주는게 좋다.

목표상태의 i번째 말과 초기상태의 i번째 말이 다를 경우 필요한 색깔의 말을 +1 해준다.

( 초기상태의 말은 하얀색인데 목표상태의 말은 검은색일경우 black + 1 )

 

여기서부터는 패턴을 찾아야 하는데, 시간이 좀 걸렸다.

검은색 말과 하얀색 말을 세트로 묶으면 한번의 작업만 소요되고 세트로 묶이지 않을경우는

말 한개당 한번의 작업이 필요하다.

 

세트로 묶던 묶이지 않던, 말 하나당 한번의 작업이 필요하다.

( 애초에 필요한 색깔의 말들을 모았기 때문 )

따라서 검은색 말과 하얀색 말 개수의 최댓값이 최소작업횟수가 된다.