백준 13413번 : 오셀로 재배치(그리디)

문제 요약:

흑 또는 백 이루어진 로봇을 흑백 교차하는 로봇으로 변형하는 것.

두가지 작업 중 하나를 골라 진행할 수 있다.

1. 배치된 말 중 임의의 2개의 말을 골라 서로의 위치를 바꾼다.

2. 말 1개를 들어 뒤집어 놓아 색상을 변경한다.

 

INPUT: 각 테스트 케이스 당: 말의 갯수, 초기 상태, 목표 상태

OUTPUT : 필요한 작업 최소횟수

 

풀이:

summ에서는 알파벳이 다른 위치의 총 갯수를, subt에서는 'B'-->'W'인 경우와 'B'-->'W'인 경우를 부호가 반대로 되게 표시해줌.

sum(subt)를 통해, 1, -1인 자리들은 합쳐서 0이 됨. 즉, 자리 교환.

남은 1 또는 -1들의 갯수가 뒤집어야 하는 갯수.

def solve(ini, fin):
    ini_int = [int(i == 'W') for i in ini]
    fin_int = [int(i == 'W') for i in fin]
    summ = [ (ini_int[i]+fin_int[i])%2 for i in range(len(ini_int))]
    subt = [ (ini_int[i]-fin_int[i]) for i in range(len(ini_int))]
    total = summ.count(1)
    turn = abs(sum(subt))
    return (total-turn)//2+turn

if __name__ == '__main__':
    T = int(input())
    answers = []
    for _ in range(T):
        N = int(input())
        ini = list(input())
        fin = list(input())
        ans = solve(ini, fin)
        answers.append(ans)
    for ans in answers:
        print(ans)

 

----------------------------------------------------------------------

다른 풀이:

이게 더 알고리즘에 어울리는 풀이 같다.

for 문을 각 인덱스에 대해서 검사하는데, 서로의 위치가 같은 경우: 패스, 바꿔야 하는 경우: 'B'/ 'W'를 나눠서 카운트 해준다. 

둘 중 더 많은 것의 갯수가 정답.( min(cnt_B, cnt_W) 만큼은 자리를 바꿔주면 되고, 남은 자리에 대해서 스위치.)

백준 ID jrucl2d 님 것을 참조

def solve(ini, fin):
    cnt_B = 0
    cnt_W = 0
    for i in range(len(ini)):
        if ini[i]==fin[i] : continue
        if ini[i]=='W': cnt_W += 1
        elif ini[i]=='B' : cnt_B += 1
    return max(cnt_W, cnt_B)