문제분석
종이 크기는 1(3의 0승), 3(3의 1승), 9(3의 2승)... 형태로 주어짐
각각 1*1, 3*3, 9*9 크기로 이루어짐
k=1 일 때 종이를 자를 수 없음 (1을 3으로 나누면 몫이 0)
k=3 일때 종이를 한 번 자를 수 있음 (3을 3으로 나누면 몫이 1, 즉 1*1 9개로 나눠짐)
k=3의 n승일때 n번 종이를 자를 수 있음
1. 함수식
func(n, x, y)
n : 종이 크기
x : 모든 종이가 똑같은 값인지 검사할 행
y : 모든 종이가 똑같은 값인지 검사할 열
func(3, 0, 0)으로 예시를 들어보면
(0,0) 값을 기준으로 삼고 3*3 모든 종이의 칸과 비교
종이의 각 칸이 모두 같은 수로 되어있다면 해당 수의 개수 1 증가 후 재귀함수 종료
종이의 각 칸이 모두 같은 수로 되어있지 않다면 종이 크기를 3으로 나눠서 감소
만약 종이의 크기가 1이라면 3으로 나누면 몫이 0이기 때문에 더 이상 나눌 수 없으므로 재귀함수 종료
func(3/3, 0, 0) -> func(1, 0, 0) -> func(1/3, 0, 0) X
2. Base condition
종이의 크기를 3으로 나누었을때 몫이 0인 경우 재귀함수 종료, 종이의 크기가 1인 경우에 해당됨
코드
#include<iostream>
using namespace std;
// 종이의 각 칸
int board[2188][2188];
// -1[0], 0[1], 1[2] 채워진 종이 개수
int cnt[3];
void func(int n, int x, int y) {
// 종이의 각 칸이 모두 같은 수로 되어있는지 체크
bool sameValCk = true;
for (int i = x; i < n + x; i++) {
for (int j = y; j < n + y; j++) {
if (board[x][y] != board[i][j]) {
sameValCk = false;
break;
}
}
if (!sameValCk) break;
}
if (sameValCk) {
cnt[board[x][y] + 1] += 1;
return;
}
else {
int z = n / 3;
// 1*1은 한칸이기 때문에 무조건 똑같은 수로 이루어져 있어서 조건을 체크할 필요 없음
// 9등분에 대해서 재귀함수 실행
// 다른 값이랑 비교할 좌표를 각 9등분한 시작위치로 세팅하기 위해서는 x축, y축 방향으로 이동시 z를 더해줘야됨
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
func(z, x + i*z, y + j*z);
}
}
}
}
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(0);
// 1.입력
int N;
cin >> N; // 3의 n승 형태
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
}
}
// 2.로직
func(N, 0, 0);
// 3.출력
cout << cnt[0] << '\n' << cnt[1] << '\n' << cnt[2];
return 0;
}
int z = n / 3;
// 1*1은 한칸이기 때문에 무조건 똑같은 수로 이루어져 있어서 조건을 체크할 필요 없음
// 9등분에 대해서 재귀함수 실행
// 다른 값이랑 비교할 좌표를 각 9등분한 시작위치로 세팅하기 위해서는 x축, y축 방향으로 이동시 z를 더해줘야됨
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
func(z, x + i*z, y + j*z);
}
}
9*9 행렬을 9등분을 하게 되면 3*3 행렬 9개로 분할되는데 모든 3*3 행렬의 시작위치가 다르기 때문에 z만큼의 값을 곱해줘야 한다. x와 y를 더해주는 이유는 9등분을 한 지점에서 다시 종이의 개수를 계산하기 때문인데 x와 y를 더해주지 않으면 무조건 (0,0)의 위치부터 시작하기 때문이다.
이해하기 어렵다면 9*9 행렬을 9 등분하고 (0,3) 위치에 있는 3*3 행렬을 다시 9 등분하는 과정을 살펴보면 확인할 수 있다.
특이사항
무조건 재귀함수로만 구현해야 된다고 생각해서 반복문을 쓰지 않아야 된다고 생각을 했었는데 반복문 따로 재귀함수 따로 사용해야 되는 부분이 다른 경우도 있기 때문에 적절히 섞어서 쓰면 된다.
