[백준] 14391 종이 조각 - Brute Force / Java

• 문제 링크

14391번: 종이 조각

 

• 풀이 과정

n * m 크기의 사각형을 조각낼 수 있는 모든 경우의 수는 1 << n * m - 1 가지이므로

사각형을 조각낼 수 있는 모든 경우을 탐색하는 반복문(0 = bit < (1 << n * m)) 내부에

가로(0 = i < n, 0 = j < m)와 세로 방향(0 = j < m, 0 = i < n)을 나누어 탐색한다.

 

두 반복문의 현재 위치(cur = i * m + j) 를 비트 연산(bit & (1 << cur)을 수행하여

해당 비트 연산 결과가 0 일 경우 가로 방향 사각형, 1 일 경우 세로 방향 사각형에 포함됨을 의미하므로,

사각형이 탐색 방향으로 이어진 만큼 자릿수를 늘려가며 사각형의 값을 구해 tmp 에 저장한다.

 

만약 사각형의 이어짐이 끊길 경우, 구해진 tmp 값을 sum 에 누적 및 0으로 초기화한다.

 

이렇게 각각의 조각낼 수 있는 모든 경우의 수에서 구해진 조각의 합을

매번 최대값(maxSum) 으로 갱신시켜 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] map = new int[n][m];

        for (int i = 0; i < n; i++) {
            String input = br.readLine();
            for (int j = 0; j < m; j++)
                map[i][j] = input.charAt(j) - '0';
        }

        int maxSum = 0;
        for (int bit = 0; bit < (1 << n * m); bit++) {
            int sum = 0;

            for (int i = 0; i < n; i++) {
                int tmp = 0;
                for (int j = 0; j < m; j++) {
                    int cur = i * m + j;

                    if ((bit & (1 << cur)) == 0)
                        tmp = tmp * 10 + map[i][j];
                    else {
                        sum += tmp;
                        tmp = 0;
                    }
                }

                sum += tmp;
            }

            for (int j = 0; j < m; j++) {
                int tmp = 0;
                for (int i = 0; i < n; i++) {
                    int cur = i * m + j;

                    if ((bit & (1 << cur)) != 0)
                        tmp = tmp * 10 + map[i][j];
                    else {
                        sum += tmp;
                        tmp = 0;
                    }
                }

                sum += tmp;
            }

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

        bw.write(maxSum + "\n");
        bw.flush();
    }

}