[JAVA] 백준 14391번: 종이 조각 ( 초급 2-34 ) - fail

문제

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

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

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

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

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

입력

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

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

출력

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

 

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

public class baekjoon14391 {
    private static int row;
    private static int col;
    private static Character[][] info;
    private static int[][] bit;
    private static int result = 0;

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

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

        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        info = new Character[row][col];
        bit = new int[row][col];

        for (int i = 0; i < row; i++) {
            String temp = br.readLine();
            for (int j = 0; j < col; j++) {
                info[i][j] = temp.charAt(j);
            }
        }
        permutation(0);
        System.out.println(result);
    }

    private static void permutation(int index) {
        if (index == row * col) {

            // 0은 가로 1은 세로
            int currentTotal = 0;
            for (int i = 0; i < row; i++) {
                int tempRowTotal = 0;
                for (int j = 0; j < col; j++) {
                    if (bit[i][j] == 0) {
                        tempRowTotal *= 10;
                        tempRowTotal += Character.getNumericValue(info[i][j]);
                    } else if (bit[i][j] == 1) {
                        currentTotal += tempRowTotal;
                        tempRowTotal = 0;
                    }
                }
                currentTotal += tempRowTotal;
                tempRowTotal = 0;
            }

            for (int i = 0; i < col; i++) {
                int tempColTotal = 0;
                for (int j = 0; j < row; j++) {
                    if (bit[j][i] == 0) {
                        currentTotal += tempColTotal;
                        tempColTotal = 0;
                    } else if (bit[j][i] == 1) {
                        tempColTotal *= 10;
                        tempColTotal += Character.getNumericValue(info[j][i]);
                    }
                }
                currentTotal += tempColTotal;
                tempColTotal = 0;
            }
            if (currentTotal > result) {
                result = currentTotal;
            }
            return;
        }
        int tempRow = index / col;
        int tempCol = index % col;

        bit[tempRow][tempCol] = 0;
        permutation(index + 1);
        bit[tempRow][tempCol] = 1;
        permutation(index + 1);
    }
}