bj14391(종이 조각) - 브루트 포스, 재귀

처음 보자마자 한숨이 나온 문제이다.

재귀를 통해 문제를 접근해야겠다고 생각했지만, 쉽지 않았다.

 

재귀 메서드

->재귀 메서드는 x + 1의 방향으로 진행한다. x가 M에 도달하면, y+1을 한다.

->x 방향으로 진행하며, 가로 방향 직사각형은 true, 세로 방향 직사각형은 false로 둔다.

->매 칸마다, 가로로 할지 세로로 할 지를 결정한다.

-> 0,0에서 시작하여, 빠짐없이 종이를 나눌 수 있다.

 

합 메서드

-> 합은 가로(true) 조사, 세로(false) 조사 따로따로한다.

-> for(y+1 for(x+1) ) 이런 형식의 for문으로 가로부터 조사한다.

-> true가 끊기기 전까지 수를 10의 자리씩 늘려간다.

-> 모든 가로를 더한 값을 저장

->세로 역시 마찬가지, x+1( y+1) 이런 형식으로 세로 조사

->그렇게 나온 가로 세로의 합을 Math.max로 aswer에 넣는다.

 

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

public class Main {
    static int N, M, max;
    static int[][] paper;
    static boolean[][] visited;
    static StringTokenizer stringTokenizer;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        initialize();
        recursive(0,0);
        System.out.println(max);
    }
    private static void recursive(int y, int x){
        //현재 y가 끝일때, 지금까지 만들어진 종이 조각을 더하고 return
        if(y == N){
            sum();
            return;
        }

        int nextX = (x+1) % M; //다음 진출할 x
        int nextY = (x+1 == M) ? y+1 : y;   //다음 진출할 y => x가 끝에 다다르면, y+1

        //매 칸마다 가로로 할지 세로로 할지 결정
        visited[y][x] = true;   //가로로 진행
        recursive(nextY, nextX);
        visited[y][x] = false;  //세로로 진행
        recursive(nextY, nextX);
    }
    private static void sum(){
        int sum = 0;
        for(int y = 0; y < N; y++){
            int width = 0;
             for(int x = 0; x < M; x++){
                 if(visited[y][x]){
                    width *= 10;
                    width += paper[y][x];
                 }else{
                     sum += width;
                     width = 0;
                 }
             }
            sum += width;
        }

        for(int x = 0; x < M; x++){
            int length = 0;
            for(int y = 0; y < N; y++){
                if(!visited[y][x]){
                    length *= 10;
                    length += paper[y][x];
                }else{
                    sum += length;
                    length = 0;
                }
            }
            sum += length;
        }

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

    private static void initialize() throws IOException {
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());
        paper = new int[N][M];
        visited = new boolean[N][M];
        for(int y = 0; y < N; y++){
            String line = bufferedReader.readLine();
            for(int x = 0; x < M; x++){
                paper[y][x] = Character.getNumericValue(line.charAt(x));
            }
        }
    }
}