[백준] 14391번 종이조각 비트마스크로 풀어보기 : Programming Story

www.acmicpc.net/problem/14391

문제

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.

영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.

입력

첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)

둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.

출력

영선이가 얻을 수 있는 점수의 최댓값을 출력한다.

예제와 제한이 궁금하다면 위의 링크를 클릭해 자세한 사항을 알아보자.

이 문제는 비트마스크로 풀 수 있다.

비트마스크란 비트연산을 사용하여 정수로 집합을 나타내는 것이다.

예를 들어 {1,3,4,5,9} 가 사용이 되었다면 우리는 이를 정수로 01000111010 이라고 표현할 수 있다. (binary digit이 0자리부터 시작한다고 생각했을 때, 1번째 자리, 3번째자리, 4번째 자리, 5번째 자리, 9 번째 자리를 1로 표시하는 것이다)

이 경우에는 n*m 의 칸이 있으니 각각을 자릿수로 하는 n*m-1자리 정수를 만들 수 있는 것이다.

각각의 칸에 대해서 가로로 묶을 것인지, 세로로 묶을 것인지 정하면 되는데 양자택일의 문제이므로

가로로 묶을 경우 해당 자릿수의 숫자를 0으로, 세로로 묶을 경우 해당 자릿수의 숫자를 1로 정했다고 가정하겠다.

 int sum=0;
 //가로 찾기
            for(int i=0; i<n; i++){
                int current=0;
                for(int j=0; j<m; j++){
                    int k=i*m+j;
                    if ((s&(1<<k))==0){ //해당 칸이 가로일 경우
                        current=current*10+a[i][j];
                    }
                    else{ //해당 칸이 세로일 경우: current를 0으로
                        sum+=current;
                        current=0;
                    }
                }
                sum+=current;
            }

위 링크는 가로로 묶은 숫자들을 다 더하는 경우이다.

i 번째 열과 j 번째 행에 대해서 이중 for문을 설계하였고, 가로의 경우 하나의 열에 대해서 쭉 이어지는 식으로 구해야 하기 때문에 열을 나타내는 i가 바깥 for문이 되는 것이다.

해당 칸이 가로일 경우 current 숫자 뒤에 해당 칸에 있는 숫자를 더하고, 그렇지 않을 경우 세로를 나타내는 것이기 때문에 sum에다가 지금까지의 수를 더해준 뒤 current는 초기화해준다.

세로의 경우도 마찬가지로 하되, 열과 행의 순서만 바꾸면 된다.

 //세로
            for(int j=0;j<m; j++ ){
                int current=0;
                for(int i=0; i<n; i++){
                    int k=i*m+j;
                    if ((s&(1<<k))!=0){
                        current=current*10+a[i][j];
                    }
                    else{
                        sum+=current;
                        current=0;
                    }
                }
                sum+=current;
            }

위의 내용을 종합해보았을 때 전체 코드는

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc= new Scanner (System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int [][]a=new int [n][m];
        for(int i=0; i<n; i++){
            String s=sc.next();
            for(int j=0; j<m; j++){
                a[i][j]=s.charAt(j)-'0';
            }
        }
        int ans=0;
        //가로: 0, 세로: 1
        for(int s=0; s<(1<<(n*m)); s++){
            int sum=0;
            //가로 찾기
            for(int i=0; i<n; i++){
                int current=0;
                for(int j=0; j<m; j++){
                    int k=i*m+j;
                    if ((s&(1<<k))==0){
                        current=current*10+a[i][j];
                    }
                    else{
                        sum+=current;
                        current=0;
                    }
                }
                sum+=current;
            }
            //세로
            for(int j=0;j<m; j++ ){
                int current=0;
                for(int i=0; i<n; i++){
                    int k=i*m+j;
                    if ((s&(1<<k))!=0){
                        current=current*10+a[i][j];
                    }
                    else{
                        sum+=current;
                        current=0;
                    }
                }
                sum+=current;
            }
            ans=Math.max(sum, ans);
        }
        System.out.println(ans);
    }
}

이렇게 작성할 수 있다.