[Java] 백준 1285번: 동전 뒤집기

[문제 바로 가기] - 동전 뒤집기

📌 유형 : 비트마스킹 + 그리디

개인적으로 어려웠던 문제지만 비트 연산에 대해 익히기 좋았던 것 같다.

💡 아이디어

먼저 N개의 각 행을 뒤집을지 안 뒤집을지 결정을 하는데, 이때 비스마스킹을 사용한다.

bit는 0부터 1<<N - 1까지의 값으로 1<<N은 Math.pow(2, N)과 같은 값이다.
즉, bit는 000부터 001, 010, 011, ... , 111까지의 값이 되는 것이다.

000 : 아무 행도 뒤집지 않음
001 : 0번째 행만 뒤집음
010 : 1번째 행만 뒤집음
011 : 0, 1번째 행만 뒤집음
100 : 2번째 행만 뒤집음
101 : 0, 2번째 행만 뒤집음
110 : 1, 2번째 행만 뒤집음
111 : 모든 행을 뒤집음

sum은 현재 bit에서의(특정 행을 뒤집고 나서의) T의 최소 개수이며 back은 특정 열을 뒤집고 나서의 T의 개수이다.

		for (int bit = 0; bit < (1 << N); bit++) {
			int sum = 0;
			
			for (int col = 0; col < N; col++) {
				int back = 0; // T인 동전 개수
				
				for (int row = 0; row < N; row++) {
					int cur = coins[row][col];
					
					/*
					 * bit = 011(=3)일 경우 (0번째, 1번째 행만 뒤집음)
					 * 
					 * bit & (1 << 0) != 0이므로 0번째 행 뒤집음
					 * bit & (1 << 1) != 0이므로 1번째 행 뒤집음
					 * bit & (1 << 2) == 0이므로 2번째 행 뒤집지 않음
					 */
					
					if ((bit & (1 << row)) != 0) cur ^= 1;
					
					if (cur == 0) back++; // T인 동전 개수 세기
					
				}
				
				// 각 열에서 T의 개수와 H의 개수 중 적은 쪽을 뒤집음
				sum += Math.min(back, N - back);
			}
			answer = Math.min(answer, sum);
			
		}

(bit & (1 << row)) != 0는 비트마스크에서 row번째 비트가 0이 아닌지 확인하는 조건이다. 0이 아닐 경우 해당 행을 뒤집어야 하므로 cur ^= 1을 수행해준다.
나는 동전의 값들을 0과 1로 저장해두었기 때문에 cur ^= 1을 수행하면 0은 1, 1은 0으로 바뀐다.

	sum += Math.min(back, N - back);

cur이 0일 경우 뒷면인 경우이므로 back의 개수에 추가한 뒤, back의 개수와 N - back의 개수 중 작은 값을 sum에 저장한다.

---

풀이

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

/**
 * 백준 1285번 동전 뒤집기
 * 1. N개의 각 행을 뒤집을지 안 뒤집을지 결정
 * 2. 각 경우에 따라 각 열이 뒷면이 더 많을 경우 뒤집기
 */

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[][] coins = new int[N][N];
		
		for (int i = 0; i < N; i++) {
			String[] str = br.readLine().split("");
			
			for (int j = 0; j < N; j++) {
				if (str[j].equals("H")) coins[i][j] = 1;
				else coins[i][j] = 0;
			} 
		}
		
		int answer = Integer.MAX_VALUE;
		
		// 1 << N = Math.pow(2, N) = 2의 N제곱
		for (int bit = 0; bit < (1 << N); bit++) {
			int sum = 0;
			
			for (int col = 0; col < N; col++) {
				int back = 0; // T인 동전 개수
				
				for (int row = 0; row < N; row++) {
					int cur = coins[row][col];
					
					/*
					 * bit = 011(=3)일 경우 (0번째, 1번째 행만 뒤집음)
					 * 
					 * bit & (1 << 0) != 0이므로 0번째 행 뒤집음
					 * bit & (1 << 1) != 0이므로 1번째 행 뒤집음
					 * bit & (1 << 2) == 0이므로 2번째 행 뒤집지 않음
					 */
					
					if ((bit & (1 << row)) != 0) cur ^= 1;
					
					if (cur == 0) back++; // T인 동전 개수 세기
					
				}
				
				// 각 열에서 T의 개수와 H의 개수 중 적은 쪽을 뒤집음
				sum += Math.min(back, N - back);
			}
			answer = Math.min(answer, sum);
			
		}
		
		System.out.println(answer);
	}
}