[백준] 14391번 종이 조각 비트마스킹 풀이(자바 풀이)

문제

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

14391번: 종이 조각

풀이

N,M이 최대 4이므로 최대 2(가로,세로)^16=65536의 경우의 수가 있으므로 브루트포스 방식으로 해결가능하다.

재귀형식으로 각 원소를 가로로 택할지 세로로 택할지 선택할 수 있겠지만, 비트마스킹을 사용하면 더 간단하다.

 

예를 들어 아래와 같은 예제를 보자.

[그림 1] 비트마스킹 예시

비트가 0이면 해당 숫자는 가로, 1이면 세로라고 판단하자. [그림 1]의 왼쪽그림은 오른쪽처럼 나타낼 수 있다.

이를 마치 한 줄처럼 나타낸다면 s = 0001 1101 1111 0011 로 나타낼 수 있다. 

 

이때 각 조각의 합을 구하는 것은 가로조각과 세로조각을 나누어서 구하면 된다. 

 

가로조각은 가로줄을 기준으로 탐색하면서 비트가 0이라면 자릿수를 잘 계산해서 더해주면 된다. 

세로조각은 세로줄을 기준으로 탐색하면서 비트가 1이라면 자릿수를 잘 계산해서 더해주면 된다.

 

모든 경우의 수를 판단해야 하므로, 위와 같은 과정을 s = 0000 0000 0000 0000 ~ 1111 1111 1111 1111 까지 판단하면 된다. 

 

코드를 보면 더 이해가 쉽다.

코드

import java.util.*;
import java.io.*;
 
public class Baekjoon_14391 {
    static int N,M;
    static int paper[][];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        paper = new int[N][M];
        
        for(int i=0; i<N; i++) {
            String str = br.readLine();
            for(int j=0; j<M; j++) {
                paper[i][j] = str.charAt(j) - '0';
            }
        }
        
        int ans = 0;
        
        for(int s=0; s<(1<<(N*M)); s++) {
            int sum = 0;
            /* 가로(0) 찾기 */
            for(int i=0; i<N; i++) {
                int cur = 0;
                for(int j=0; j<M; j++) {
                    int k = i*M+j;    
                    if( (s&(1<<k)) ==0 ) {    // s의 k번째 비트가 0이면-> 해당 숫자는 가로
                        cur*= 10;    
                        cur += paper[i][j];    
                    }else {    // 해당 숫자는 세로
                        sum += cur;
                        cur = 0;
                    }
                }
                sum += cur;
            }
            
            /* 세로(1) 찾기 */
            for(int j=0; j<M; j++) {
                int cur = 0;
                for(int i=0; i<N; i++) {
                    int k = i*M +j;
                    if( (s&(1<<k)) != 0) {    // s의 k번째 비트가 1이면-> 해당 숫자는 세로
                        cur *= 10;
                        cur += paper[i][j];
                    }else {    // 해당 숫자는 가로
                        sum += cur;
                        cur = 0;
                    }
                }
                sum += cur;
            }
            ans = Math.max(ans, sum);
        }
        
        System.out.println(ans);        
    }
 
}

결과