백준 1285번: 동전 뒤집기

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

 

앞 뒤로 이루어진 동전이 NxN 행렬 형태로 주어질 때, 행 혹은 열 단위로 뒤집어서 뒷면의 최소 갯수를 출력하는 문제이다.

처음에는 단순히 다 뒤집으면 되지 않을까? 생각했지만, 20x20 만 되어도 2^(20 * 20)의 경우의 수가 발생되어 시간 초과가 발생하여 반려하였다. 그러한 경우의 수 중 어떠한 행을 뒤집을지 정하면 열들을 뒤집는 최선의 경우의 수는 정해진다는 것을 알게 되었다. 원하는 행이 뒤집어 진 후, 특정 열을 뒤집는 경우는 뒷면의 갯수가 최소가 되는 경우일 때만 뒤집으면 되기 때문이다.

 

이러한 과정을 최적화하기 위해 각 열을 하나의 정수로 저장한다. cols[j]의 i번째 비트는 i행 j열의 동전 상태를 의미한다.

int[] cols = new int[N];
for (int i = 0; i < N; i++) {
    String line = br.readLine();
    for (int j = 0; j < N; j++) {
        if (line.charAt(j) == 'T') {
            cols[j] |= (1 << i);
        }
    }
}

 

 

행 뒤집기는 cols[j]와 뒤집을 행들의 집합 mask를 XOR 연산하여 행 뒤집기를 한 번에 계산한다. 이를 빠르게 하기 위해 Integer.bitCount()를 사용한다.

int answer = Integer.MAX_VALUE;

for (int mask = 0; mask < (1 << N); mask++) {
    int currentTotalTails = 0;
    
    for (int j = 0; j < N; j++) {
        int tailCount = Integer.bitCount(cols[j] ^ mask);
        currentTotalTails += Math.min(tailCount, N - tailCount);
    }
    
    if (currentTotalTails < answer) {
        answer = currentTotalTails;
    }
}

 

 

최종 코드는 다음과 같다.

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

public class 동전뒤집기1285 {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] cols = new int[N];
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < N; j++) {
                if (line.charAt(j) == 'T') {
                    cols[j] |= (1 << i);
                }
            }
        }
        
        int answer = Integer.MAX_VALUE;
        
        for (int mask = 0; mask < (1 << N); mask++) {
            int currentTotalTails = 0;
            
            for (int j = 0; j < N; j++) {
                int tailCount = Integer.bitCount(cols[j] ^ mask);
                currentTotalTails += Math.min(tailCount, N - tailCount);
            }
            
            if (currentTotalTails < answer) {
                answer = currentTotalTails;
            }
        }
        
        System.out.print(answer);
    }
}