[백준 1780] 종이의 개수

www.acmicpc.net/problem/1780

1780번: 종이의 개수

정답률도 비교적 높고 쉬웠던 문제!

종이가 정사각형 모양으로 계속 잘리므로 길이를 /3해서 진행해준다.

 

#include <stdio.h>
#include <cmath>

using namespace std;

int n;
int arr[3000][3000];

int answer[3];

bool isValid(int len, int row, int col)
{
  int cmp = arr[row][col];

  for (int i = row; i < row + len; i++)
  {
    for (int j = col; j < col + len; j++)
    {
      if (cmp != arr[i][j])
      {
        return false;
      }
    }
  }
  answer[cmp + 1]++;
  return true;
}

void cutPaper(int len, int row, int col)
{
  if (isValid(len, row, col))
  {
    return;
  }

  len = len / 3;
  for (int i = 0; i < 3; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      cutPaper(len, row + len * i, col + len * j);
    }
  }
}

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]);
    }
  }

  cutPaper(n, 0, 0);

  for (int i = 0; i < 3; i++)
  {
    printf("%d\n", answer[i]);
  }
  return 0;
}