[BaekJoon] 14391 종이 조각 (Java)

1.  문제 링크

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

2.  문제

요약

• 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있는데, 종이는 1 x 1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있습니다.
• 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있습니다.
• 영선이는 직사각형을 겹치지 않는 조각으로 자르려고 하였는데, 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양입니다.
• 길이가 N인 조각은 N자리 수로 나타낼 수 있는데, 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것입니다.
• 종이를 적절히 잘라서 조각의 합을 최대로 할 때의 합을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 4보다 작거나 같은 종이 조각의 세로 크기 N과 가로 크기 M이 주어지고 두 번째 줄부터 N개의 줄에 종이 조각이 주어집니다. 각 칸에 쓰여있는 숫자는 0부터 9까지 중 하나입니다.
• 출력: 첫 번째 줄에 영선이가 얻을 수 있는 점수의 최댓값을 출력합니다.

3.  소스코드

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

public class Main {
    static int N, M;
    static int[][] map;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
        map = new int[N][M];

        for(int row = 0; row < N; row++) {
            String info = scanner.nextLine();
            for(int col = 0; col < M; col++)
                map[row][col] = info.charAt(col) - '0';
        }
    }

    static void solution() {
        int answer = 0;

        for(int bit = 0; bit < (1 << (N * M)); bit++) {
            int sum = sumRow(bit);
            sum += sumCol(bit);

            answer = Math.max(answer, sum);
        }

        System.out.println(answer);
    }

    static int sumRow(int bit) {
        int sum = 0;

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

            for(int col = 0; col < M; col++) {
                if((bit & (1 << (row * M + col))) == 0) {
                    temp *= 10;
                    temp += map[row][col];
                } else {
                    sum += temp;
                    temp = 0;
                }
            }

            sum += temp;
        }

        return sum;
    }

    static int sumCol(int bit) {
        int sum = 0;

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

            for(int row = 0; row < N; row++) {
                if((bit & (1 << (row * M + col))) != 0) {
                    temp *= 10;
                    temp += map[row][col];
                } else {
                    sum += temp;
                    temp = 0;
                }
            }

            sum += temp;
        }

        return sum;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}

4.  접근

• 각 칸에 0과 1이라는 값을 대입시켜 해당 칸이 가로 조각인지 세로 조각인지를 나타냅니다.
  • 0이면 가로 조각을, 1이면 세로 조각을 나타냅니다.
  • 이 때, 각 수는 비트마스킹을 이용해 표현할 것인데, 0000...00부터 1111...11까지로 표현할 것입니다.
    • 예를 들어, N이 2, M이 4라면 00000000부터 11111111까지로 표현됩니다.
      • 이 때, 각 자리의 숫자는 N x M의 종이에서 행의 인덱스를 row, 열의 인덱스를 col이라고 한다면 (row * M) + col 위치의 숫자를 나타냅니다.
    • 0000...00부터 1111...11까지 모든 경우에 대해 각 조각이 나타내는 숫자의 합을 구하여 그 중 가장 큰 경우를 구합니다.