[PS] BOJ1285 동전뒤집기 ( BitMasking ) With JAVA

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

1285번: 동전 뒤집기

 

◎ 문제풀이

 

[백준(BOJ)] #1285- 동전 뒤집기 (파이썬, PyPy3)

(  여러 포스팅을 찾아 보았는데 위 포스팅이 개념을 가장 잘 설명한 것 같다. )

 

동전은 행과 열로 뒤집을 수 있을 때, 가장 뒷면(T)이 적게 나오는 경우를 찾아야 한다. 모든 경우를 따져야 한다. 그러므로 행과 열로 뒤집는 모든 경우의 수를 탐색하는 방법을 찾아야 한다. 

 

행은 2가지 경우가 있다.

 

1) 행을 뒤집는 경우

2) 행을 뒤집지 않는 경우 

 

행이 n개 있다면 나올 수 있는 경우의 수는 2를  n번 곱한 2ⁿ가지 이다. 이를 비트연산으로 표현하면 1<<n이 된다. 1을 왼쪽으로 n번 쉬프트한다는 의미이다. 이진수는 한번 왼쪽으로 쉬프트를 할때마다 2가 곱해진다. 그러므로 1<<n은 2ⁿ과 같다. 

 

n이 3라고 가정하자. 그럼 1<<3은 8이다. 행이 3개 일때 나올 수 있는 경우의 수는 8가지이다. 

 

000 : 어떤 행도 뒤집지 않는 경우

001 : 첫번째 행을 뒤집는 경우

010 : 두번째 행을 뒤집는 경우

100 : 세번째 행을 뒤집는 경우

011 : 첫번째, 두번째 행을 뒤집는 경우

110 : 두번째, 세번째 행을 뒤집는 경우

101 : 첫번째, 세번째 행을 뒤집는 경우

111 : 첫번째, 두번째, 세번째 행을 뒤집는 경우

 

이진수의 각 자리를 행의 순서와 매핑하면 위와 같이 정리할 수 있다. 이렇게 하면 행을 뒤집는 모든 경우의 수를 고려할 수 있다. 8가지 경우 중 뒷면이 가장 적게 나오는 경우를 골라야 한다. 

 

그럼 열을 고려해보자. 

 

행의 8가지 경우 중 하나가 선택되었을 때, 열을 뒤집어야 한다. 단 조건이 있다. 뒷면이 최소가 되도록 하는 것이 목적이므로 행을 뒤집은 결과가 뒷면이 앞면보다 많다면 뒤집고 적다면 그대로 둔다. 

 

001 경우라고 가정하자.

 

TTH

HTT

THT

 

001은 첫번째 행만 뒤집는다. 그러므로 아래와 같다.

 

HHT

HTT

THT

 

그럼 이제 열을 하나씩 보자. 

 

첫번째 열은 T가 H보다 적으니 그대로 둔다. 

두번째 열도 T가 H보다 적으니 그대로 둔다. 

세번째 열은 T가 H보다 많으니 뒤집는다. 

 

HHH

HTH

THH

 

001의 경우, T의 개수는 2이다. 

 

이렇게 8가지 경우를 모두 찾아 최솟값을 구하면 된다. 

 

 

 

◎ 코드

import java.io.*;
import static java.lang.Math.min;

//BOJ1285 동전뒤집기
public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static int n;
    static char[][] map;

    public static void main(String[] args) throws IOException {
        input();
        solution();
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        map = new char[n][n];

        for (int i = 0; i < n; i++) {
            map[i] = br.readLine().toCharArray();
        }
    }

    public static void solution() throws IOException {
        int ans = Integer.MAX_VALUE;
        for(int bitCase = 0; bitCase<(1<<n);bitCase++){ // 행을 뒤집는 경우의 수
            int sum = 0;
            for(int j=0;j<n;j++){ // 열을 기준으로 뒤집기 
                int count = 0;
                for(int i=0;i<n;i++){
                    char tmp = map[i][j];
                    if(( bitCase & (1<<i) ) != 0) { // 행뒤집기, i번째 행이 1이면 뒤집는다. ( &(AND) 연산자로 1여부를 판단 )
                        tmp = reverse(tmp); // 행을 뒤집는 경우의 수에 포함되는 행의 값이면 뒤집는다.
                    }
                    if(tmp == 'T')  count += 1; 
                }
                sum += min(count,n-count); // 행을 뒤집은 결과로 열을 뒤집을지 결정 ( count : 안 뒤집는다. n-count : 뒤집는다. )
            }
            ans = min(ans,sum); // 행을 뒤집는 경우 중 최솟값이 답이다. 
        }
        bw.write(String.valueOf(ans));
        bw.flush();
        bw.close();
        br.close();
    }

    public static char reverse(char value){
        if( value=='T') return 'H';
        else return 'T';
    }
}