[백준] 1285. 동전 뒤집기 (비트마스킹/Java)

[백준] 1285. 동전 뒤집기

 

📌 풀이 과정

동전의 상태가 앞(H), 뒤(T) 2가지 뿐이기 때문에 각 위치를 2진수로 표현이 가능하다.

H = 0, T = 1로 설정하고 문제를 풀었다.

그리고 각 행과 열은 뒤집느냐, 뒤집지 않느냐 두가지 경우로 나눠지기에

행을 먼저 완전탐색한 이후에, 열 기준으로 T의 갯수를 카운트해 뒤집을지 말지 판단을 하면 된다.

 

1. 동전 상태를 비트로 저장

N개의 행을 정수 배열 coin[]에 저장해서 각 행을 하나의 N비트 정수로 표현했다.

예를 들어 `HTT(앞면, 뒷면, 뒷면)`인 경우

1. H → 0
2. T → 01
3. T → 011 (2진수) = 3 (10진수)

 

2. 행을 뒤집는 연산

비트를 사용하기 때문에 행을 뒤집는다는 것은 각 비트를 반전시키는 것과 같기 때문에  NOT 연산 `~`을 사용했다.

011을 뒤집으면

`011(T, T, H)` → `100(H, H, T)`

 

3. 열에서 뒤집을 동전 개수 계산

행을 뒤집은 후, 각 열에서 T의 개수를 세고,

T의 개수와 H의 개수 중 작은 값을 선택해 최소값을 구하면 된다.

((coin[j] & (1 << N - i - 1))) != 0

위 식을 사용해 j번째 행에서 i번째 열의 상태를 확인할 수 있는데

예를 들어, `coin[j] = 011 (T, T, H)` 이고 `i = 1`(가운데 열)이라면

1. (1 << (3 - 1 - 1)) = (1 << 1) = 010
2. 011 & 010 = 010 (0이 아니라면 T)

이렇게 비트 연산을 통해 각 열에서 T의 개수를 세고, 전체 최소 횟수를 갱신할 수 있다.

 

✨ 제출 코드

메모리: 15544 KB

시간: 396 ms

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

public class Main {

    static int N, answer;
    static int[] coin;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        coin = new int[N];

        for (int i = 0; i < N; i++) {
            char[] input = br.readLine().toCharArray();
            for (int j = 0; j < N; j++) {
                coin[i] = coin[i] << 1;
                if (input[j] == 'T') // 뒷면인 경우 1을 더함
                {
                    coin[i] = coin[i] | 1;
                }
            }
        }

        answer = Integer.MAX_VALUE;
        reverseHang(0);
        System.out.println(answer);
    }

    private static void reverseHang(int idx) {
        if (idx == N) { // 행 뒤집기 탐색이 끝난 경우
            int sum = 0;
            for (int i = 0; i < N; i++) { // 열

                int cnt = 0; // 뒷면(T)의 갯수
                for (int j = 0; j < N; j++) { // 현재 열의 각 행 확인
                    if (((coin[j] & (1 << N - i - 1))) != 0) {
                        cnt++;
                    }
                }

                sum += Math.min(cnt, N - cnt);
            }
            answer = Math.min(answer, sum);
            return;
        }

        coin[idx] = ~coin[idx]; // idx행 뒤집기
        reverseHang(idx + 1);
        coin[idx] = ~coin[idx]; // 뒤집은 idx행 원상 복구
        reverseHang(idx + 1);
    }
}

 

🗂️ References

백준 1285 C++ 동전 뒤집기

[백준 1285] - 동전 뒤집기(Kotlin)[골드1]