BOJ 13413 오셀로 재배치 (파이썬)

실버 4

 

문제 풀이

처음에 '아 그럼 저 조건대로 그냥 풀면 되겠구나!' 하고 다른건 바꾸고 돌려가며 풀어보았다. 하지만 풀리지가 않았다..

결국 또 해답을 보고야 말았다. 하지만 다음번엔 제발 이 풀이를 떠올리라고 정리해본다. (실버 4면서 떠올리기 개 어렵다)

 

결국엔 자리를 바꾸는 방법이 최소수를 구하기에 완벽하다.

 

일단 두 문자열을 입력받고, 같은 인덱스에 서로 다른 문자들을 체크해줄 리스트에 넣어준다.

그 후에, 뽑아온 리스트를 정렬해준다.

그러니까,

이런 상황일때 두개의 리스트에는 board_check = [ B, B, B ] 가 들어갔을테고,  match_check = [ W,W,W ]가 들어갔을테다.

이상태에서 for 문을 돌리고, 인덱스의 문자가 같을 경우엔 0.5를 더하고, 다를경우엔 1을 더해준다.

정렬한 두 리스트를 비교하여 순회 할 때 같은 돌이라면 반대 돌의 같은것이 분명히 존재한다. 따라서 이런 공식이 나온다.

 

# 오셀로 재배치
import sys
input = sys.stdin.readline

T = int(input())

while T > 0:
    N = int(input())
    text = input().rstrip()
    board = list(text)
    text = input().rstrip()
    match = list(text)
    cnt = 0
    check_board = []
    check_match = []
    for i in range(len(board)):
        if board[i] != match[i]:
            check_board.append(board[i])
            check_match.append(match[i])
    check_match.sort()
    check_board.sort()

    for i in range(len(check_board)):
        if check_board[i] == check_match[i]:
            cnt += 0.5
        else:
            cnt += 1
    print(int(cnt))
    T -= 1

https://kkk4872.tistory.com/140 

[백준 13413 파이썬] 그리디 알고리즘 오셀로 재배치

이 분 블로그를 참고했다.

 

하..그리디 너무 어렵다.. 많이 풀어보자