[백준] 14391 종이 조각 java

문제

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

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int[][] arr;
    static boolean[][] marked;
    static int n, m, total, max;

    public static void main(String[] args) throws IOException {
        init();
        dfs(0, 0);
        System.out.println(max);
    }

    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        max = Integer.MIN_VALUE;
        st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        total = n * m;
        arr = new int[n][m];
        marked = new boolean[n][m];
        for(int i = 0; i < n; i++) {
            String str = br.readLine();
            for(int j = 0; j < m; j++) {
                arr[i][j] = str.charAt(j) - '0';
            }
        }
    }

    static void dfs(int x, int y) {
        if(x == n) {
           check();
           return;
        }
        //가로, 세로
        marked[x][y] = true;
        if(y+1 == m) {
            dfs(x+1, 0);
        } else {
            dfs(x, y+1);
        }

        marked[x][y] = false;
        if(y+1 == m) {
            dfs(x+1, 0);
        } else {
            dfs(x, y+1);
        }

    }

    static void check() {
        int sum = 0;
        int colSum, rowSum;
        //가로
        for(int i = 0; i < n; i++) {
            colSum = 0;
            for(int j = 0; j < m; j++) {
                if(marked[i][j]) {
                    colSum *= 10;
                    colSum += arr[i][j];
                } else {
                    sum += colSum;
                    colSum = 0;
                }
            }
            sum += colSum;
        }

        //세로
        for(int i = 0; i < m; i++) {
            rowSum = 0;
            for(int j = 0; j < n; j++) {
                if(!marked[j][i]) {
                    rowSum *= 10;
                    rowSum += arr[j][i];
                } else {
                    sum += rowSum;
                    rowSum = 0;
                }
            }
            sum += rowSum;
        }

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

    static int stoi(String s) {return Integer.parseInt(s);}
}

dfs 완전탐색 문제이다.

 

처음에 가로, 세로 별로 길이가 최대인 가로, 세로들만 나열했을 때 최적해가 나올줄 알고 짰으나 당연히 반례가 존재했다.

 

그렇다면 가로, 세로별로 각각 자리마다 길이도 다르게 해주어야 하는데 이 부분에서 어떻게 구현하지 고민하다가 못풀 것 같아서 다른 분의 풀이를 보았다.

 

1. 각 지점마다 가로, 세로의 상태를 가진다.

2. DFS로 모든 경우의 수를 마킹해준다.

3. 모든 곳에 마킹이 완료되면, 가로, 세로 별 값들을 구한다.

4. 모두 더해서 MAX를 갱신해준다.

 

나는 하나씩 값들을 구해서 하려고 했는데 그럴 필요 없이 마킹만 먼저 해놓은 다음에 값을 구하면 되는 것 이었다.

비트마스크로도 가능하다는데 비트마스크를 배우고 나서 한번 풀어봐야겠다.