[코딩테스트][백준] 🔥 백준 1285번 "동전 뒤집기" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🛠️ 미해결

• 풀이시간 : 2시간 이상
• 아이디어 구상 : 기존의 행렬 문제와 비슷하다고 생각해서 전부다 뒤집을려고 하되 필요한 부분만 뒤집으면 된다고 생각했다. 그 이유는 동전을 두번다 뒤집게 되면 모든 동전이 두번 뒤집히기 때문에 원래대로 돌아오기 때문이다.
• 행을 먼저 따지고 열을 따지는 아이디어 : 처음에 행을 뒤집는 모든 경우에 따라 열을 뒤집는 모든 경우를 결정해본다. 즉, $2^{20}*2^{20}$의 시간복잡도가 걸린다고 생각하였기에 불가능하다는 생각은 하였다. 하지만 한쪽만 전부 고려해보고 나머지 한쪽은 최적화한다는 아이디어는 생각하지 못하였다.
• 왜? : 2의 20승이면 무조건 터진다고 생각하였기 때문에 넘어갔다는 점이 가장 크다. 실제로는 1,000,000정도 이기 때문에 연산을 고려해볼 수 있지만 이를 간과했다. 실제로 연산을 고려해보는 방법을 써보아야겠다. 또한 같이 따지는 아이디어가 불가능할 경우, 나누어서 시도해보려는 시도를 해봐야겠다. 무조건적으로 동시에 반영된다고 생각해서 따로 시도하였다. 왜냐하면 순서에 영향을 받는다고 생각했기 때문이다. 이런 부분에서 사고의 오류가 발생한 것이 중심이다. 실제로 순서를 바꾸어 보았을 때, 영향을 끼치는지를 판단하고 독립적이라면 이를 나누어서 시도하려고 해봐야 한다. 예를 들어 한행과 열을 뽑아보고 이를 순서를 바꿔서 뒤집어봤을 때, 결과가 같다면 순서에 영향이 없는 독립적인 것이다.
• 추가적인 아이디어의 이해 : 이것 왜에도 한쪽을 전부 경우의 수에 고려해본다고 하였다고 하여도 다른 한 쪽을 최적화시키는 아이디어도 이해하는데 꽤나 오래걸렸다. 즉 열에서 뒤집었을 때 최소가 되는 숫자만 구하는 것이다. 즉 400내로 가능한 것이다. 4억이라는 연산횟수가 걸리지만 약 20초가 수행된다... 하지만 단순히 열의 1의 수만을 count해서 1과 0이 적은 쪽을 세는 것만으로 최소의 0을 구하는 것이 가능하다는 점이다. 이부분은 이해가 안되지만 시간안에 가능하다.

🕒 Python 풀이시간: x

N = int(input())
coins = [[0] * N for _ in range(N)]
inputArr = [list(input()) for _ in range(N)]

# 초기 입력 값으로 coins 배열 초기화
for i in range(N):
    for j in range(N):
        if inputArr[i][j] == 'H':
            coins[i][j] = 1

# 행 반전 함수
def reverse_row(arr, i):
    for j in range(N):
        arr[i][j] = 1 - arr[i][j]

# 열의 뒤집힌 비트 카운트
def count_column_flips(arr):
    total_flips = 0
    for j in range(N):
        cnt = sum(arr[i][j] for i in range(N))
        total_flips += min(cnt, N - cnt)  # 최적의 열 반전 횟수 선택
    return total_flips

answer = float('inf')

# 모든 행 반전 조합 시도
for mask in range(1 << N):
    # 원본 배열의 복사본 생성
    tmp = [row[:] for row in coins]

    # 비트마스크를 이용해 각 행을 반전
    for i in range(N):
        if mask & (1 << i):
            reverse_row(tmp, i)

    # 최소 열 반전을 계산
    flips = count_column_flips(tmp)
    answer = min(answer, flips)

print(answer)

최소한의 뒷면! 동전 뒤집기 문제! 🪙🔄

동전을 한 행이나 열을 뒤집어서 최소한의 동전만 뒷면을 보게 만드는 문제이다. 이 때, 어떻게 뒤집느냐에 따라 순서가 동전을 뒤집는데 영향을 줄 수 있다고 생각할 수 있으나 어떻게 뒤집든 같은 결과가 나오기 때문에 동전을 뒤집는 순서는 영향을 주지 않는다.

먼저 모든 행을 뒤집는 모든 경우의 수 즉, 모든 부분집합을 구하는 방식으로 접근한다. 비트를 사용해서 모든 부분집합을 기준으로 할 배열을 복사해두고 행을 그 케이스에 따라 뒤집는다. 그리고 그 경우에서의 최소로 뒷면이 나오는 갯수를 구한다.

뒷면이 최소가 되는 갯수는 각 열에 대해서 H와 T의 갯수 중 작은 것을 구하는 것이다. 결국 뒤집든 안 뒤집든 적은 쪽이 뒤집고 나서의 T가 될 것이기 때문에 꼭 뒤집지 않더라고 우리는 각 열에서의 갯수를 구할 수 있다. 이를 다 더한 후 답을 갱신 시키면 된다.

이렇게 Python으로 백준의 "동전 뒤집기" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊