BOJ#14391 종이 조각

BOJ#14391 종이 조각

* 문제

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

* 풀이

모든 경우의 수를 다 따져보아야 합니다.

각 조각은 가로 또는 세로이므로 2^(N*M)의 경우의 수가 있습니다.

문제 풀이에 비트마스크를 이용하였습니다.

예를 들어, 3x3 종이에서 아래와 같은 경우라면

1 1 0

1 1 0

1 0 1

-> 1 1 0 1 1 0 1 0 1 으로 표현할 수 있습니다.

즉, 0 0 0 0 0 0 0 0 0 부터 1 1 1 1 1 1 1 1 1 까지

모든 경우의 수는 아래와 같이 뽑아낼 수 있습니다.

        // 모든 경우를 다 해보기 : 2^NM
        for (int state = 0; state < (1 << N * M); state++) {

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/71290744cb349a0e513e7d70f6d1a6297f3038ab/BOJ%2314391_PieceOfPaper/src/Main.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * BOJ#14391 종이 조각
 * https://www.acmicpc.net/problem/14391
 */

public class Main {

    public static void main(String[] args) throws IOException {

        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] map = new int[N][M];

        for (int i = 0; i < N; i++) {

            String s = br.readLine();
            for (int j = 0; j < M; j++) {

                map[i][j] = s.charAt(j) - '0';
            }
        }

        // Solve
        int maxSum = 0;

        // 모든 경우를 다 해보기 : 2^NM
        for (int state = 0; state < (1 << N * M); state++) {

            int sum = 0;

            // 가로 계산
            for (int row = 0; row < N; row++) {

                int rowSum = 0;

                for (int col = 0; col < M; col++) {

                    int colIdx = row * M + col;

                    if ((state & (1 << colIdx)) == 0) {

                        rowSum = rowSum * 10 + map[row][col];
                    } else {

                        sum += rowSum;
                        rowSum = 0;
                    }
                }

                sum += rowSum;
            }

            // 세로 계산
            for (int col = 0; col < M; col++) {

                int colSum = 0;

                for (int row = 0; row < N; row++) {

                    int rowIdx = col + row * M;

                    if ((state & (1 << rowIdx)) != 0) {

                        colSum = colSum * 10 + map[row][col];
                    } else {

                        sum += colSum;
                        colSum = 0;
                    }
                }

                sum += colSum;
            }

            maxSum = maxSum < sum ? sum : maxSum;
        }

        System.out.println(maxSum);
    } // ~main
}