[JAVA] 백준 14391 - 종이 조각

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

 

 

낱개의 종이구간을 가로 또는 세로로 보는 전략을 생각 못하였다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int N;
    static int M;
    static int[][] map;
    static int[][] sliced;
    static boolean[][] visited;
    static int ans = Integer.MIN_VALUE;
    static int sum;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] lines = br.readLine().split(" ");
        N = Integer.parseInt(lines[0]);
        M = Integer.parseInt(lines[1]);
        map = new int[N][M];
        sliced = new int[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            lines = br.readLine().split("");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(lines[j]);
                sliced[i][j] = -1;
            }
        }
        dfs(0,0);
        System.out.println(ans);
    }
    static void dfs(int x , int y){
        if(x == N) { //종료 조건
            visited = new boolean[N][M];
            ans = Math.max(ans, check());
            return;
        }
        if(y == M){ // 반복
            dfs(x + 1 , 0);
            return;
        }
        sliced[x][y] = 0; //가로
        dfs(x , y + 1);

        sliced[x][y] = 1;
        dfs(x, y + 1);


    }

    private static int check() {
        int result = 0;
        int temp;
        // 가로로 자른 종이들 합 구하기
        for (int i = 0; i < N; i++) {
            temp = 0;
            for (int j = 0; j < M; j++) {
                // 가로로 자른 종이일 때
                if (sliced[i][j] == 0) {
                    temp *= 10;
                    temp += map[i][j];
                }
                // 가로로 자른 종이가 아닐때
                else {
                    // 전에 구한 가로로 자른 종이의 합을 최종 합 더해줌
                    result += temp;
                    // 다시 가로 종이의 합을 0으로 초기화
                    temp = 0;
                }
            }
            result += temp;
        }

        // 세로로 자른 종이들 합 구하기
        for (int i = 0; i < M; i++) {
            temp = 0;
            for (int j = 0; j < N; j++) {
                // 세로로 자른 종이일 때
                if (sliced[j][i]== 1) {
                    temp *= 10;
                    temp += map[j][i];
                }
                // 세로로 자른 종이가 아닐때
                else {
                    // 전에 구한 세로로 자른 종이의 합을 최종 합 더해줌
                    result += temp;
                    // 다시 세로 종이의 합을 0으로 초기화
                    temp = 0;
                }
            }
            result += temp;
        }


        return result;
    }


}