백준 1285번 - 동전 뒤집기

문제

백준 1285번 - 동전 뒤집기

---

아이디어

재귀 호출 무작정 브루트포스로 탐색하면 시간 초과가 발생한다. 모든 행과 열에 대해서 뒤집거나 안 뒤집거나를 따지면 2^40이다.
따라서 행에 대해서만 브루트포스 탐색하고, 열에 대한 확인은 그리디하게 탐색한다.

0. 입력

int[][] arr = new int[n][n];

for (int i = 0; i < n; i++) {
    
    char[] chars = br.readLine().toCharArray();
    
    for (int j = 0; j < n; j++) {
        arr[i][j] = (chars[j] == 'H') ? 0 : 1;
    }
}

• 각 행과 열에 H면 0, T면 1로 저장한다.

1. 각 행 브루트포스 탐색

int ans = n * n;

for (int bit = 0; bit < (1 << n); bit++) {
    turnRows(arr, n, bit);
    ans = Math.min(ans, solve(arr, n));
    turnRows(arr, n, bit);
}

System.out.println(ans);

• 어떤 행을 뒤집을 것인지는 비트로 간편하게 표현할 수 있다.
• 최솟값 탐색을 위해 뒤집고, 다음 탐색을 위해 다시 원상복구 시켜준다.

2. turnRows 메서드

private static void turnRows(int[][] arr, int n, int bit) {

    for (int i = 0; i < n; i++) {
   
        if (((bit & (1 << i)) != 0)) {
        
            for (int j = 0; j < n; j++) {            
                arr[i][j] = 1 - arr[i][j];
            }
        }
    }
}

• AND 연산으로 어떤 행을 뒤집을 것인지 판단할 수 있다.
• 각 행과 열은 0 또는 1로 되어 있기 때문에 1에서 값을 빼주는 것만으로 뒤집는 효과를 볼 수 있다.

3. solve 메서드

private static int solve(int[][] arr, int n) {

    int total = 0;	//전체 T의 개수
    
    for (int i = 0; i < n; i++) {
    
        int count = 0;	//각 열에 T의 개수
        
        for (int j = 0; j < n; j++) {
            if (arr[j][i] == 1) {	//i, j 아님 주의 => j, i 임
                count++;
            }
        }
        
        total += Math.min(count, n - count);
    }
    
    return total;
}

• 특정 행을 뒤집었을 때 각 열의 상태를 확인한다.
• 각 열에서 T의 개수를 세어 해당 열을 뒤집을지 말지 판단한다.
• count는 뒤집지 않았을 때, n - count는 뒤집었을 때 T의 개수가 된다.
• 즉, 그리디하게 T가 더 적은 경우만 결괏값에 누적해준다.

---

예상 시간 복잡도

• 예상 시간 복잡도 : O(2^N x N^2)

---

코드 구현 - 자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BJ_1285 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[][] arr = new int[n][n];

        for (int i = 0; i < n; i++) {

            char[] chars = br.readLine().toCharArray();

            for (int j = 0; j < n; j++) {
                arr[i][j] = (chars[j] == 'H') ? 0 : 1;
            }
        }

        int ans = n * n;

        for (int bit = 0; bit < (1 << n); bit++) {
            turnRows(arr, n, bit);
            ans = Math.min(ans, solve(arr, n));
            turnRows(arr, n, bit);
        }

        System.out.println(ans);
    }

    private static void turnRows(int[][] arr, int n, int bit) {

        for (int i = 0; i < n; i++) {
            if (((bit & (1 << i)) != 0)) {

                for (int j = 0; j < n; j++) {

                    arr[i][j] = 1 - arr[i][j];
                }
            }

        }
    }

    private static int solve(int[][] arr, int n) {

        int total = 0;

        for (int i = 0; i < n; i++) {

            int count = 0;

            for (int j = 0; j < n; j++) {
                if (arr[j][i] == 1) {
                    count++;
                }
            }

            total += Math.min(count, n - count);
        }

        return total;
    }
}

코드 구현 - 파이썬

n = int(input())
arr = [[0 if ch == 'H' else 1 for ch in input()] for _ in range(n)]

ans = n * n


def turnRows(arr, n, bit):
    for i in range(n):
        if bit & (1 << i):
            for j in range(n):
                arr[i][j] = 1 - arr[i][j]


def solve(arr, n):
    total = 0

    for i in range(n):
        count = 0
        for j in range(n):
            if arr[j][i] == 1:
                count += 1

        total += min(count, n - count)

    return total


for bit in range(1 << n):
    turnRows(arr, n, bit)
    ans = min(ans, solve(arr, n))
    turnRows(arr, n, bit)

print(ans)