동전 뒤집기 알고리즘 - dongjeon dwijibgi algolijeum

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

1285번: 동전 뒤집기

첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위

www.acmicpc.net

Approach

Greedy + Bitmask 문제이다.

주요 로직은 다음과 같다. N x N 행렬이고, sum은 뒷면 동전의 총 개수이다.

• 행을 기준으로 뒤집을 행을 선택한다. (이 부분은 2^n 개수 만큼 존재한다.)
  • 101 이라면 0, 2번째 행을 뒤집는다.
• 이제 선택한 행들을 뒤집을 건데, 열을 기준으로 먼저 뒤집는다.
  • 101 이라면, 0,1,2 열 순서대로 0번째 행 요소와 2번째 행 요소를 뒤집는다.
• 선택한 행들을 기준으로 하나의 열을 모두 뒤집었으면, 그 열에 동전 뒷면이 몇개인지를 센다.
  • 앞면 동전과 뒷면 동전 중 작은 것을 sum에 더한다.
  • 왜냐하면 뒷면 동전이 많을 경우, 해당 열을 뒤집어야 뒷면 동전 개수가 최소가 되기 때문이고, 앞면 동전이 많을 경우, 해당 열을 뒤집지 않는 것이 뒷면 동전 개수가 최소가 되기 때문이다.

이렇게 하면, 모든 행과 열을 뒤집어보는 결과와 같은 결과를 낸다. 이것이 가능한 이유는 행을 뒤집는 것과 열을 뒤집는 것이 각각 독립적이기 때문이다. (서로에게 영향을 끼치지 않는다는 뜻이다.)

Code

import java.io.*;

/**
 *  No.1285: 동전 뒤집기
 *  Hint: Bitmask + Greedy
 */

public class BOJ1285 {
    static int n;
    static char[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter 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();
        }

        int ans = Integer.MAX_VALUE;
        // 길이가 n인 2진수 비트로 어떤 행들을 뒤집을지 선택(모든 경우의 수를 다 수행함)
        for (int bit = 0; bit < (1 << n); bit++) {
            int sum = 0;
            // 뒤집기를 선택한 행들을 뒤집는다.
            for (int b = 0; b < n; b++) {
                int back = 0;
                // 단 열을 기준으로 뒤집는다.
                for (int a = 0; a < n; a++) {
                    char cur = map[a][b];

                    // 뒤집기로 선택한 행의 열이라면 뒤집는다.
                    if ((bit & (1 << a)) != 0) {
                        cur = reverse(a, b);
                    }

                    if (cur == 'T') {   // 동전이 뒷면이면 카운트한다.
                        back++;
                    }
                }
                // b열을 뒤집었을 때, 뒤집지 않았을 때 중 동전의 개수가 더 적은 것을 누적합한다.
                sum += Math.min(back, n - back);
            }
            // 선택된 행들을 뒤집었을 때, 뒷면 동전의 최소 개수를 구한다.
            ans = Math.min(ans, sum);
        }
        // 위의 로직이 가능한 이유는, 행끼리의 뒤집기는 서로 영향을 주지 않고
        // 열끼리의 뒤집기 또한 서로 영향을 주지 않기 때문이다.

        bw.write(String.valueOf(ans));
        bw.close();
        br.close();
    }

    static char reverse(int y, int x) {
        if (map[y][x] == 'T') {
            return 'H';
        } else {
            return 'T';
        }
    }
}

1285번: 동전 뒤집기 (acmicpc.net)

1285번: 동전 뒤집기

첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위

www.acmicpc.net

1. 비트마스크로 동전의 가로를 뒤집고 안뒤집은 경우를 모두 확인한다.

2. 세로에서 뒤집힌 동전의 수가 더 적으면 그대로 놔두고 더 많으면 뒤집는다.

n = int(input())
coin = [list(input()) for _ in range(n)]
ans = n * n + 1

for bit in range(1 << n):
    tmp = [coin[i][:] for i in range(n)]
    for i in range(n):
        if bit & (1 << i):
            for j in range(n):
                if tmp[i][j] == 'H':
                    tmp[i][j] = 'T'
                else:
                    tmp[i][j] = 'H'

    tot = 0
    for i in range(n):
        cnt = 0
        for j in range(n):
            if tmp[j][i] == 'T':
                cnt += 1
        tot += min(cnt, n-cnt)
    ans = min(ans, tot)

print(ans)

www.acmicpc.net/problem/1285

1285번: 동전 뒤집기

첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위

www.acmicpc.net

그리디, 브루트포스, 비트마스킹을 이용한다.

처음에 문제를 잘못읽었는데 동전을 선택하는 것이 아니라 행이나 열을 선택하는 것이었다.

문제를 제대로 읽고나니 풀이방법이 바로 떠올랐다.

풀이 방법:

비트마스킹을 활용하여 20개의 조합(100만 정도임)을 전부 해볼 것인데,

만약 행과 열 모두 브루트포스로 돌리게되면 (100만*100만)으로 시간초과가 난다.

그래서, 열만 조합을 돌려 뒤집어주고,

행은 뒷면인 동전의 개수만 세서 만약 앞면인 동전의 개수보다 많다면 뒤집는 방식으로 하였다.

시간초는 6초가 주어지지만 1초내로 풀린다.

코드:

알고리즘 / / 2021. 2. 12. 01:16

www.acmicpc.net/problem/1285

1285번: 동전 뒤집기

첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위

www.acmicpc.net

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

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

우선 동전을 행과 열에 대해서 뒤집을 수 있기 때문에 행을 뒤집을 수 있는 경우, 즉 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 중에 적은 값을 더해주면 쉽게 풀 수 있는 문제이다.