백준 1780 종이의 개수 c++ // 재귀함수, 일반식도출

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

1780번: 종이의 개수

1. 내 정답코드

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

int n,ret1,ret2,ret3, a[2200][2200];

//시작좌표~끝좌표(시작좌표+n)까지 돌면서 모두같은지 검사
bool all_same(int n, int y, int x) {

	int first = a[y][x];
	for (int i = y; i < y + n; ++i) {
		for (int j = x; j < x + n; ++j) {
			if (a[i][j] != first) {
				return false;
			}
		}
	}

	return true;

}

//함수정의 : 크기n*n, 시작좌표 
void go(int n, int y, int x) {
	//기저사례
	if (all_same(n,y,x)) {

		if (a[y][x] == -1) {
			ret1++;
		}
		if (a[y][x] == 0) {
			ret2++;
		}
		if (a[y][x] == 1) {
			ret3++;
		}
		return;
	}

	int one_third = n / 3;
	//재귀식
	//9칸으로 나눈후 각각칸의 시작좌표를 구했음.
	go(one_third,y,x);
	go(one_third, y, x+ one_third);
	go(one_third, y, x+ one_third*2);
	go(one_third, y+ one_third, x);
	go(one_third, y+ one_third, x+ one_third);
	go(one_third, y+ one_third, x+ one_third*2);
	go(one_third, y+ one_third*2, x);
	go(one_third, y+ one_third*2, x+ one_third);
	go(one_third, y+ one_third*2, x+ one_third*2);
}

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

	cin >> n;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> a[i][j];
		}
	}

	go(n, 0, 0);

	cout << ret1 << "\n" << ret2 << "\n" << ret3;

}

 

2. 바킹독님 코드

go 재귀식 노가다 부분을

일반식으로 정리한 후

for문을 이용하여 처리하였다....

 int n = z / 3;
  for (int i = 0; i < 3; i++)
  for (int j = 0; j < 3; j++)
    solve(x + i * n, y + j * n, n);

// Authored by : cpprhtn
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/b8488e82105d49e89ca6f39fd8ee665b
#include <bits/stdc++.h>
using namespace std;

int N;
int paper[2200][2200];
int cnt[3]; //-1, 0, 1로 채워진 종이 갯수

//해당 종이 내부에 같은 숫자로만 채워졌는지 확인하는 함수
bool check(int x, int y, int n) {
  for (int i = x; i < x + n; i++)
  for (int j = y; j < y + n; j++)
    if (paper[x][y] != paper[i][j])
    return false;
  return true;
}
void solve(int x, int y, int z)
{
  if (check(x, y, z)) {
    cnt[paper[x][y] + 1] += 1;
    return;
  }
  int n = z / 3;
  for (int i = 0; i < 3; i++)
  for (int j = 0; j < 3; j++)
    solve(x + i * n, y + j * n, n);
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> N;
  for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
    cin >> paper[i][j];
  solve(0, 0, N);
  for (int i = 0; i < 3; i++) cout << cnt[i] << "\n";
}