백준 14391 종이조각 C++

문제

www.acmicpc.net/problem/14391

14391번: 종이 조각

문제

#include<bits/stdc++.h>

using namespace std;

int n, m, answer, board[4][4], arr[4][4];

void input()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for(int j = 0; j < m; j++)
        {
            board[i][j] = s[j] - '0';
        }
    }
}

void check()
{
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        int tempSum = 0;
        for(int j = 0; j < m; j++)
        {
            if(arr[i][j])
            {
                tempSum = tempSum * 10 + board[i][j];
            }
            else
            {
                sum += tempSum;
                tempSum = 0;
            }
        }
        sum += tempSum;
    }

    for(int i = 0; i < m; i++)
    {
        int tempSum = 0;
        for(int j = 0; j < n; j++)
        {
            if(arr[j][i] == 0)
            {
                tempSum = tempSum * 10 + board[j][i];
            }
            else
            {
                sum += tempSum;
                tempSum = 0;
            }
        }
        sum += tempSum;   
    }

    answer = max(answer, sum);
}

void go(int pos)
{
    if(pos > n * m - 1)
    {
        check();
        return;
    }

    int y = pos % n;
    int x = pos / n;

    arr[y][x] = 1;
    go(pos + 1);

    arr[y][x] = 0;
    go(pos + 1);
}

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

    input();
    go(0);

    cout << answer << '\n';
    
	return 0;
}