[백준] 1285번 동전 뒤집기 문제 쉽게 푸는방법? : Programming Story

www.acmicpc.net/problem/1285

문제는 위의 링크를 클릭하면 볼 수 있다.

이 문제는 비트마스크를 활용해서 풀 수 있다.

우선 동전을 행과 열에 대해서 뒤집을 수 있기 때문에 행을 뒤집을 수 있는 경우, 즉 2의 N가지를 비트마스크를 통해서 표현해보는 것이다. (각 행에 대해서 뒤집는다/안뒤집는다 두 가지 choice가 있기 때문에) 그러면 비트마스크로 나타내면 0부터 n-1자리 수까지 즉 (1<<n)-1 까지 숫자가 있는것이고 k 자리 수가 1이라는 것은 k 번째 행을 뒤집는 것을 표현한 것이라고 할 수 있다.

그래서 0부터 (1<<n)-1까지 모든 경우에 대해서 for문을 돌리고, 또 이중 for문으로 열에 대해서 뒤집을지 뒤집지 않을지를 결정해준다. 하지만 열의 경우에는 T의 최소개수를 고르는 것이기 때문에 현재 T와 H 중 최소값을 sum에다가 더해주면 된다. 이유는 T의 최소값을 구하는 것인데 만약 현재 T가 적게 있다면 그 숫자만큼 더해주면 되는 것이고, 만약 H가 더 적게 있다면 한번 뒤집었다고 생각하고 H의 개수를 단순히 더해주면 된다.

그런뒤에 비트마스크의 모든 경우마다 답을 구해주고 그것이 최소가 되는 경우를 찾아주면 된다.

이를 코드화한 것은 아래와 같다.

import java.util.*;

public class Main{
    static char change(char x){
        if (x=='H'){
            return 'T';
        }
        else {
            return 'H';
        }
    } 
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        char a[][]=new char[n][n];
        for(int i=0; i<n; i++){
            String s=sc.next();
            for(int j=0; j<n; j++){
                a[i][j]=s.charAt(j);
            }
        }
        int ans=n*n; //최소값을 구해야 하므로 최대부터 시작
        for(int bit=0; bit<(1<<n); bit++){
            int sum=0;
            for(int i=0; i<n; i++){//모든 세로에 대해서 구함
                int tail=0;
                for(int j=0; j<n; j++){//모든 가로
                    char cur=a[j][i];
                    if ((bit&(1<<j))!=0){//행을 뒤집어준다는 뜻
                        cur=change(cur);
                    }
                    if (cur=='T'){tail++;}
                }
                sum+=Math.min(tail, n-tail);
            }
            if (sum<ans){
                ans=sum;
            }
        }
        System.out.println(ans);
    }
}

즉 이 문제는 한 행에 대해서 어떻게 change할지를 비트마스크로 결정해놓고 그 다음에 각 열에 대해서 T와 H 중에 적은 값을 더해주면 쉽게 풀 수 있는 문제이다.