[BOJ] 14391. 종이 조각 (Java)

[BOJ] 14391. 종이 조각 (Java)

Problem

제출일 : 2020-03-14

문제 풀이 시간 : 1H 45M

난이도 : ★★★

---

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

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

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

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

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

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

Input

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

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

Output

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

Example

input

2 3
123
312

output

435

Solution & Inpression

조금 어려웠던 문제...

모든 경우의 수를 탐색해 최대값을 찾는 과정으로 문제를 푸려 생각을 했지만 모든 경우의 수를 어떻게 만들어야 할지 생각하기가 조금은 힘들었다.

N과 M이 최대 4로 각각의 칸이 종이의 가로 이거나 세로인 2가지 종류가 있기에 모든 경우의 수는 $2^{16}$이기 때문에 완전탐색이 가능했다.

2차원 배열을 1차원 배열로 만들어 인덱스 조작을 편하게 작업했다. r행 i열은 r*M + i로 표현할수 있다.

Code

언어 : JAVA

메모리 : 17152 kb

실행 시간 : 160 ms

import java.util.Scanner;

public class Main {
    static int N, M, ans;
    static int[] map;
    static boolean[] visit;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N * M];
        for (int i = 0; i < N; i++) {
            String str = sc.next();
            for (int j = 0; j < M; j++) {
                map[i * M + j] = str.charAt(j) - '0';
            }
        }

        visit = new boolean[N * M];
        ans = 0;
        solve(0);
        System.out.println(ans);
    }

    private static void solve(int idx) {
        if (idx == N * M) {
            check();
            return;
        }

        // 해당 좌표 선택(가로 선택)
        visit[idx] = true;
        solve(idx + 1);

        // 해당 좌표미선택(세로 선택)
        visit[idx] = false;
        solve(idx + 1);

    }

    private static void check() {
        int sum = 0, tmp = 0;

        // 가로
        for (int i = 0; i < N; i++) {
            tmp = 0;
            for (int j = 0; j < M; j++) {
                if (visit[i * M + j]) {
                    tmp *= 10;
                    tmp += map[i * M + j];
                } else {
                    sum += tmp;
                    tmp = 0;
                }
            }
            sum += tmp;
        }

        // 세로
        for (int j = 0; j < M; j++) {
            tmp = 0;
            for (int i = 0; i < N; i++) {
                if (!visit[i * M + j]) {
                    tmp *= 10;
                    tmp += map[i * M + j];
                } else {
                    sum += tmp;
                    tmp = 0;
                }
            }
            sum += tmp;
        }

        // 최대값 갱신
        ans = Math.max(ans, sum);
    }
}