백준 [C++] 14391 종이 조각

<조건 분석>

1. n과 m이 최대 4이므로 2^6 정도 경우의 수임.

 

<문제 해결 포인트>

1. 가로 세로로 나눈다는 개념을 코드로 구현하기가 까다로웠는데, 일일히 더하기로 했음.

 

2. 가로는 비트마스킹으로 체크할 수 있었음.

 

3. 사실 최대 4*4니까 16이라 아예 전체 경우의 수를 하나의 비트마스킹으로 커버할수도 있음.

 

 

 

 

<처음 풀었던 내 풀이>

#include <bits/stdc++.h>
using namespace std;

int n = 0;
int m = 0;

int board[4][4];
int flag[4];
int cnt = -1;

int cal()
{
    int ret = 0;
    for (int i = 0; i < n; i++)
    {
        int a = 1;
        int temp = 0;
        for (int j = 0; j < m; j++)
        {
            if (flag[i] & (1 << j))
            {
                temp *= a;
                temp += board[i][j];
                a = 10;
            }
            else
            {
                ret += temp;
                temp = 0;
                a = 1;
            }
        }

        ret += temp;
    }

    for (int i = 0; i < m; i++)
    {
        int a = 1;
        int temp = 0;
        for (int j = 0; j < n; j++)
        {
            if ((flag[j] & (1 << i)) == 0)
            {
                temp *= a;
                temp += board[j][i];
                a = 10;
            }
            else
            {
                ret += temp;
                temp = 0;
                a = 1;
            }
        }
        ret += temp;
    }

    return ret;
}

void combi(int depth)
{
    if (depth == n)
    {
        cnt = max(cnt, cal());
        return;
    }


    for (int j = 0; j < (1 << m); j++)
    {
        flag[depth] = j;
        combi(depth + 1);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            scanf("%1d", &board[i][j]);
        }
    }

    combi(0);

    cout << cnt << "\n";
    return 0;
}

 

 

<완전한 비트마스킹 풀이>

이건 근데 너무 어렵다. 코드 가독도 너무 힘듦.

#include <bits/stdc++.h>
using namespace std;

int n, m;
int board[4][4];
int ret = 0;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            scanf("%1d", &board[i][j]);
        }
    }

    for (int i = 0; i < (1 << n * m); i++)
    {
        int sum = 0;
        for (int j = 0; j < n; j++)
        {
            int cur = 0;
            for (int k = 0; k < m; k++)
            {
                int l = j * m + k;
                if ((i & (1 << l)) == 0)
                {
                    cur = cur * 10 + board[j][k];
                }
                else
                {
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }

        for (int j = 0; j < m; j++)
        {
            int cur = 0;
            for (int k = 0; k < n; k++)
            {
                int l = k * m + j;
                if ((i & (1 << l)))
                {
                    cur = cur * 10 + board[k][j];
                }
                else
                {
                    sum += cur;
                    cur = 0;
                }
            }
            
            sum += cur;
        }

        ret = max(ret, sum);
    }

    cout << ret << "\n";
    return 0;
}