백준 14391번 종이 조각 ( C++ )

문제

https://www.acmicpc.net/problem/14391

 

해설

모든 경우의 수를 확인하는 로직을 생각해 내야하는문제

비트 마스킹을 이용해서 해결

 

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int mp[8][8], n, m, ret;
string line;
 
int go(int num)
{
  int sum = 0;
  for (int i = 0; i < n; i++)
  {
    int tmp = 0;
    for (int j = 0; j < m; j++)
    {
      if ((num & (1 << (i * m + j))) != 0)
      {
        tmp = tmp * 10 + mp[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++)
    {
      if ((num & (1 << (i * m + j))) == 0)
      {
        tmp = tmp * 10 + mp[i][j];
      }
      else
      {
        sum += tmp;
        tmp = 0;
      }
    }
    sum += tmp;
  }
  return sum;
}
 
int main()
{
  cin >> n >> m;
  for (int i = 0; i < n; i++)
  {
    cin >> line;
    for (int j = 0; j < m; j++)
    {
      mp[i][j] = line[j] - '0';
    }
  }
 
  for (int i = 0; i < (1 << (n * m)); i++)
  {
    int tmp = go(i);
    ret = max(tmp, ret);
  }
 
  cout << ret;
}