문제

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 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

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

public class Main {
    static int n, m, answer;
    static int[][] paper;
    static boolean[][] direction;
    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());

        paper = new int[n][m];
        direction = new boolean[n][m];
        for(int i = 0; i < n; i++){
            char[] temp = br.readLine().toCharArray();
            for(int j = 0; j < m; j++){
                paper[i][j] = temp[j] - '0';
            }
        }

        answer = 0;
        folding(0, 0);
        System.out.println(answer);
    }
    static void folding(int row, int col){
        if(row == n - 1 && col == m){           
            //row == n - 1 && col == m - 1일 경우 마지막 경우를 계산하지 않기 때문에 col == m 까지로 설정해 모든 경우를 다 생각해야함
            int temp = 0, total = 0;
            //가로일 경우 계산
            for(int i = 0; i < n; i++){
                temp  = 0;      //같은 줄에서 마지막 줄까지 가로일 경우를 생각해서 temp를 초기화해주고 total에 더 해준다.
                for(int j = 0; j < m; j++){
                    if(direction[i][j]){
                        temp *= 10;
                        temp += paper[i][j];
                    }
                    else{
                        total += temp;
                        temp = 0;
                    }
                }
                total += temp;
            }
            // 세로일 경우 계산  => 회전해서 생각
            for(int i = 0; i < m; i++){
                temp = 0;
                for(int j = 0; j < n; j++){
                    if(!direction[j][i]){
                        temp *= 10;
                        temp += paper[j][i];
                    }
                    else{
                        total += temp;
                        temp = 0;
                    }
                }
                total += temp;
            }
            answer = total > answer ? total : answer;
            return;
        }
        if(col >= m){
            row++;
            col = 0;
        }
        
        direction[row][col] = true;         //가로
        folding(row, col + 1);
        
        direction[row][col] = false;        //세로
        folding(row, col + 1);
    }
}

브루투포스 마지막 문제!!
이제 그래프~