[재귀] C11 백준 1780 종이의 개수 풀이

문제

• 1780

풀이 과정

• 이 문제는 조건이 2가지가 있는데
  • 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
  • (1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
• 그렇다면 재귀 basecode는 종이가 모두 같은 수 일 때, 어떤 수로 채워졌는지 확인하고 해당 숫자(-1, 0, 1)를 카운팅
• 숫자가 다르다면 9조각으로 잘라야하는데,
  • n은 3^k꼴로 들어오기 때문에 3의 제곱인 3, 9, 27 ... 2187 로 들어옴
  • 그렇다면 (0, 0) 와 같이 종이가 시작되는 지점을 구해서 재귀 돌리면 될 듯 싶다

#include <stdio.h>
#include <stdbool.h>

#define MAX 2188

int map[MAX][MAX];

int a,b,c;

bool check(int x, int y, int size) {
    for (int i=x; i<x+size; i++) {
        for (int j=y; j<y+size; j++) {
            if (map[x][y] != map[i][j]) {
                return false;
            }
        }
    }
    return true;
}

void func(int x, int y, int size) {
    if (check(x, y, size)) {
        int temp = map[x][y];
        if (temp == -1) a++;
        else if (temp == 0) b++;
        else if (temp == 1) c++;
        return;
    }
    
    int ns = size/3;
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            func(x+i*ns, y+j*ns, ns);
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            scanf("%d", &map[i][j]);
        }
    }
    
    func(0, 0, n);
    
    printf("%d\n%d\n%d", a, b, c);
    
    return 0;
}