[ BOJ ][JAVA][14391] 종이 조각

www.acmicpc.net/problem/14391

14391번: 종이 조각

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	2725	1454	1065	54.254%

문제

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

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

아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다.

각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.

종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.

입력

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

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

출력

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

예제 입력 1

2 3
123
312

예제 출력 1

435

예제 입력 2

2 2
99
11

예제 출력 2

182

예제 입력 3

4 3
001
010
111
100

예제 출력 3

1131

예제 입력 4

1 1
8

예제 출력 4

8

코드

/*
    종이조각문제.
    n과 m이 최대 4이고 각 칸이 가로이거나 세로인 2가지 종류이므로 모든 경우의 수는 2^16승이므로 완탐 가능
    2차원 배열을 1차원배열로 만들어 인덱스 조작에 편의를 더함.
    r행 c열은 r * m + c이다.
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class p14391 {
    static int n, m, answer = 0;
    static int[] map;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        visit = new boolean[n * m];
        map = new int[n * m];
        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i * m + j] = input.charAt(j)-'0';
            }
        }

        dfs(0);
        System.out.println(answer);
    }

    static void dfs(int idx) {
        if (idx == n * m) {
            check();
            return;
        }

        // 해당 좌표 선택 -> 가로선택
        visit[idx] = true;
        dfs(idx + 1);
        visit[idx] = false;
        // 해당 좌표 미선택 -> 세로선택
        dfs(idx + 1);
    }

    static void check() {
        int sum = 0, tmp = 0;

        // 가로
        for (int i = 0; i < n; i++) {
            tmp = 0;
            for (int j = 0; j < m; j++) {
                if (visit[i * m + j]) {
                    tmp *= 10;
                    tmp += map[i * m + j];
                } else {
                    sum += tmp;
                    tmp = 0;
                }
            }
            sum += tmp;
        }

        // 세로 -> n과 m의 위치를 바꾸어 배열 회전과 동일한 효과를 본다. <<<< 핵심 포인트.
        for (int j = 0; j < m; j++) {
            tmp = 0;
            for (int i = 0; i < n; i++) {
                if (!visit[i * m + j]) {
                    tmp *= 10;
                    tmp += map[i * m + j];
                } else {
                    sum += tmp;
                    tmp = 0;
                }
            }
            sum += tmp;
        }

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

비트마스킹 풀이

import java.io.*;
import java.util.StringTokenizer;
public class Main {
    static int N, M;
    static int[][] paper;

    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        try {
            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 input = br.readLine();
                for(int j = 0; j < M; j++) {
                    paper[i][j] = input.charAt(j) - '0';
                }
            }

            int max = get_total();
            System.out.println(max);

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static int get_total() {
        int max = 0;
        for(int s = 0; s < (1 << (N * M)); s++) {
            int sum = 0;
            sum += get_hori(s);
            sum += get_vert(s);
            if(sum > max) {
                max = sum;
            }
        }
        return max;        
    }

    public static int get_hori(int s) {
        int sum = 0;
        for(int i = 0; i < N; i++) {
            int temp = 0;
            for(int j = 0; j < M; j++) {
                if((s & (1 << i * M + j)) != 0) {
                    temp *= 10;
                    temp += paper[i][j];
                }
                else {
                    sum += temp;
                    temp = 0;
                }
            }
            sum += temp;
        }
        return sum;
    }

    public static int get_vert(int s) {
        int sum = 0;
        for(int i = 0; i < M; i++) {
            int temp = 0;
            for(int j = 0; j < N; j++) {
                if((~s & (1 << j * M + i)) != 0) {
                    temp *= 10;
                    temp += paper[j][i];
                }
                else {
                    sum += temp;
                    temp = 0;
                }
            }
            sum += temp;
        }
        return sum;
    }
}