BOJ_14391_종이 조각 (Java)

[Gold III] 종이 조각 - 14391

문제 링크

성능 요약

메모리: 18520 KB, 시간: 188 ms

분류

비트마스킹, 브루트포스 알고리즘

제출 일자

2025년 2월 27일 22:06:49

문제 설명

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

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

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

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

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

입력

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

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

출력

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

문제 풀이

최대 4*4 개의 비트라고 생각하고 가로를 0, 세로를 1로 두고 숫자를 계산했다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, M, board[][], max;
    static int[] dr = {0, 1}, dc = {1, 0};
    static int[] visited;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_14391_종이조각/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new int[N][M];

        for(int i=0; i<N; i++) {
            String line = br.readLine();
            for(int j=0; j<M; j++) {
                board[i][j] = line.charAt(j) - '0';
            }
        }

        // 가로 0, 세로 1
        for(int bitmask = 0; bitmask < (1<< (N*M)); bitmask++){
            int sum = 0;
            for(int i=0; i<N; i++) {
                int curr = 0;
                for(int j=0; j<M; j++) {
                    int bitPos = i * M + j;
                    if((bitmask & (1 << bitPos)) == 0) { // 가로
                        curr *= 10;
                        curr += board[i][j];
                    }
                    else{ // 세로
                        sum += curr;
                        curr = 0;
                    }
                }
                sum += curr;
            }

            for(int j=0; j<M; j++) {
                int curr = 0;
                for(int i=0; i<N; i++) {
                    int bitPos = i * M + j;
                    if((bitmask & (1 << bitPos)) != 0) {
                        curr *= 10;
                        curr += board[i][j];
                    }
                    else{
                        sum += curr;
                        curr = 0;
                    }
                }
                sum += curr;
            }
            max = Math.max(max, sum);
        }

        System.out.println(max);
        bw.flush();
        bw.close();
        br.close();
    }
}