[Backjoon_14391] 종이조각 (Java)

문제링크

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

문제설명

문제

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

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

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

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

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

 

입력

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

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

출력

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

제한사항

제한시간	메모리제한
2초	512MB

*출처 : www.acmicpc.net

문제풀이

종이조각은 가로 또는 세로로 n*1의 길이 만큼의 숫자이다. 문제는 임의의 조각으로 나누었을 때 모든 조각의 합이 최대가 되는 값을 구하는 것이다.

조각을 내는 방법은 한칸을 가로로 놓는지 혹은 세로로 놓는지에 따라 다르므로 2^n이 된다. 이 때 가로와 세로의 최대 길이가 4이므로 모든 경우의 수를 확인하는 경우가 2^16임을 알 수 있다. 그리고 조각의 합을 수하는 방법은 판을 전부 확인하는 것으로 브루트포스 알고리즘을 활용하여 문제를 해결하여도 정해진 시간 내에 문제를 해결할 수 있다.

 

조각들이 가로인지 세로인지를 구분하기 위해 나는 이차원의 boolean 배열(paper)을 사용하였다. 

        paper[xIdx][yIdx] = true;
        if(xIdx == n-1){
            recursive(num,paper,n,m,0,yIdx+1);
        }
        else {
            recursive(num, paper, n, m, xIdx + 1, yIdx);
        }
        paper[xIdx][yIdx] = false;
        if(xIdx == n-1){
            recursive(num,paper,n,m,0,yIdx+1);
        }
        else {
            recursive(num, paper, n, m, xIdx + 1, yIdx);
        }

위 코드는 재귀를 돌리는 코드이다. num은 현재 종이조각 한칸씩 값이 들어 있는 2차원 배열 n,m은 종이의 길이이다.

xIdx와 yIdx를 주어 현재 point되고 있는 종이조각을 표현하였다. 종이조각이 2차원 배열이므로 조건문을 활용해 xIdx와 yIdx를 적당히 변경해 주며 재귀를 불러주었다. 그리고 우선 true일 때를 재귀로 돌려주고 그 다음 false로 바꾸어 다시 돌려 두가지 경우를 표현해주었다.

 

        if(yIdx == m){
            int sum = 0;
            for(int i = 0; i < n; i++){
                int cur = 0;
                for(int j = 0; j <m; j++){
                    if(paper[i][j]){
                        cur = cur*10 + num[i][j];
                    }
                    else{
                        sum += cur;
                        cur = 0;
                    }
                }
                sum += cur;
            }

재귀로 boolean값을 모두 넣는 시점은 바로 yIdx가 m이 되었을 때이다. 이 경우 모든 종이를 돌며 얼마인지 확인하여야한다.

종이들을 체크하며 같은 종이라면 10을 곱하고 해당 위치 종이의 값을 더해주는 방식으로 처리하며 가로를 처리한 후 세로를 처리해 모두 더해서 해당 값이 최대값인지 비교해주면 답을 쉽게 구할 수 있다.

구현코드

import java.util.Scanner;

public class Main {
    static int max = Integer.MIN_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();

        int[][] num = new int[n][m];

        for (int i = 0; i < n; i++) {
            String s = sc.next();
            for (int j = 0; j < m; j++) {
                num[i][j] = s.charAt(j) - '0';
            }
        }
        recursive(num,new boolean[n][m],n,m,0,0);
        System.out.println(max);
    }

    //재귀 - 어떤거 쓸지
    public static void recursive(int[][] num, boolean[][] paper, int n, int m, int xIdx, int yIdx){
        if(yIdx == m){
            int sum = 0;
            for(int i = 0; i < n; i++){
                int cur = 0;
                for(int j = 0; j <m; j++){
                    if(paper[i][j]){
                        cur = cur*10 + num[i][j];
                    }
                    else{
                        sum += cur;
                        cur = 0;
                    }
                }
                sum += cur;
            }

            for(int j = 0; j < m; j++ ){
                int cur = 0;
                for(int i = 0; i < n; i++){
                    if(!paper[i][j]){
                        cur = cur*10 + num[i][j];
                    }
                    else{
                        sum += cur;
                        cur = 0;
                    }
                }
                sum += cur;
            }
            if(max < sum){
                max = sum;
            }
            return;
        }
        paper[xIdx][yIdx] = true;
        if(xIdx == n-1){
            recursive(num,paper,n,m,0,yIdx+1);
        }
        else {
            recursive(num, paper, n, m, xIdx + 1, yIdx);
        }
        paper[xIdx][yIdx] = false;
        if(xIdx == n-1){
            recursive(num,paper,n,m,0,yIdx+1);
        }
        else {
            recursive(num, paper, n, m, xIdx + 1, yIdx);
        }
    }
}

 

시간복잡도

모든 경우의 수 : 2^n

각 경우의 수를 처리하는 방법 : n*m

O(2^n*n*m)