BOJ 14391 : 종이 조각

문제링크

풀이 요약

비트마스킹 (풀이 참조)

풀이상세

1. 2차원 배열의 숫자 정보를 1차원으로 만든다고 가정한다. 예를들어 테스트케이스 1의 경우에는 123312 가 된다. $N,M$ 의 최대는 4 이므로, 1차원 배열의 최대 길이는 16이므로 비트마스킹으로 풀이가 가능하다.

2. 현재 인덱스가 1인지 0인지를 나눈다. 0인 경우를 가로조각, 1인 경우를 세로조각으로 한다. 예를 들어 000111 인 경우는 3 크기의 가로조각이 1개, 1 크기의 세로조각이 3개로 자르는 것이다.

3. 탐색을 가로 방향과 세로 방향으로 나누어 임의의 비트에서 나오는 가로,세로 조각의 총합들 가운데 가장 큰 값이 정답이다.

#include <iostream>
#include <algorithm>
using namespace std;
string a[4];
int N, M, ans;

void input() {
    cin >> N >> M;
    string str;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
}

void solve() {
    for (int i = 0; i < (1 << (N * M)); i++) {
        // 가로
        int sum = 0;
        for (int j = 0; j < N; j++) {
            int curr = 0;
            for (int k = 0; k < M; k++) {
                if (!(i & (1 << j * M + k))) {
                    curr = curr * 10 + (int) (a[j][k] - '0');
                } else {
                    sum += curr, curr = 0;
                }
            }
            sum += curr;
        }

        // 세로
        for (int k = 0; k < M; k++) {
            int curr = 0;
            for (int j = 0; j < N; j++) {
                if ((i & (1 << j * M + k))) {
                    curr = curr * 10 + (int) (a[j][k] - '0');
                } else {
                    sum += curr, curr = 0;
                }
            }
            sum+= curr;
        }
        ans = max(ans, sum);
    }
}

void output() {
    cout << ans;
}

int main() {
    input();
    solve();
    output();
}