JAVA)14391번 종이 조각 - 브루트 포스, 비트마스크

starmk95 2020. 8. 12. 17:38
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[][] num = new int[n][m];
        for (int i=0; i<n; i++) {
            String s = sc.next();
            for (int j=0; j<m; j++) {
                num[i][j] = s.charAt(j) - '0'; // char형을 int 형으로 바꾸는 방법
            }
        }
        // 비트마스크 - 브루트포스
        // 각 칸을 가로로 놓을지 세로로 놓을지 모든 경우의 수를 확인
        int ans = 0;
        for (int i=0;i<(1<<(n*m));i++) {
            int sum = 0;
            // 가로로 놓는 경우
            for (int j=0;j<n;j++) {
                int cur = 0; // 현재 이어진 가로칸들로 구성된 수
                for (int k=0;k<m;k++) {
                    int index = j*m+k; // 2차원 배열을 1차원 배열로 보았을 때, i행 j열은 앞에 i*m+(j-1)개의 원소들이 있기 때문
                    if ((i&(1<<index)) == 0) { // 가로이면
                        cur = cur*10 + num[j][k];
                    } else {
                        sum += cur;
                        cur = 0;
                    }
                }
                sum+=cur;
            }
            // 세로로 놓는 경우
            for (int j=0;j<m;j++) {
                int cur = 0;
                for (int k=0;k<n;k++) {
                    int index = k*m+j;
                    if ((i&(1<<index)) != 0) { // 세로이면
                        cur = cur*10 + num[k][j];
                    } else {
                        sum += cur;
                        cur = 0;
                    }
                }
                sum += cur;
            }
            ans = Math.max(ans, sum);
        }
        System.out.println(ans);
    }
}