[백준 2630] 색종이 만들기

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

divide and conquer로 카테고리로 분리가 되어있지만

재귀함수를 사용하자...

 

#include <stdio.h>

using namespace std;
int n;
int arr[129][129];
int res[2];

bool isValid(int x, int y, int len)
{
  int cmp = arr[x][y];
  for (int i = x; i < x + len; i++)
  {
    for (int j = y; j < y + len; j++)
    {
      if (cmp != arr[i][j])
      {
        return false;
      }
    }
  }
  return true;
}
void ref(int x, int y, int len)
{
  if (len == 1)
  {
    res[arr[x][y]]++;
    return;
  }

  if (isValid(x, y, len))
  {
    res[arr[x][y]]++;
    return;
  }

  len /= 2;
  ref(x, y, len);
  ref(x + len, y, len);
  ref(x, y + len, len);
  ref(x + len, y + len, len);
}
int main(void)
{
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < n; j++)
    {
      scanf("%d", &arr[i][j]);
    }
  }

  ref(0, 0, n);

  printf("%d\n%d\n", res[0], res[1]);
  return 0;
}