[BOJ 2630] 색종이 만들기 - C++

✅️[문제/Problem]
https://www.acmicpc.net/problem/2630

2630번: 색종이 만들기

✅️[풀이/Explanation]

재귀 문제이다.
재귀 문제를 풀때 baseConditon(종료 조건)과  n, n+1일때 풀이에 집중해야 한다.
종료 조건은 처음 주어진 수와 반복문 내에서 배열 값이 같지 않을때 종료하도록 한다.
재귀함수에서 n/2를 호출하여 좌표값을 부르면 된다.

Solving method is the recursive function.
when unraveling a recursive problem, we should concentrate on the base_condition and when a situation of recursive is N or N+1(that is mathematical induction). The base_condition is to cease when the first given number is not equal to a number in arrays.
By visiting n/2 in recursive function(To divide into quarter arrays), we can select a coordinate. for instance, in N is 4, (0,0) -> (2,0), etc.

✅️[코드/code]

#include <bits/stdc++.h>

using namespace std;

int arr[256][256];

int N;

int ans[2];

bool calc(int n, int x, int y){

    int start = arr[x][y];

    for(int i=x; i<x+n; i++){

        for(int j=y; j<y+n; j++){

            if(start != arr[i][j]){

                return true;

            }

        }

    }

        return false;

}

void cal(int n, int x, int y){

    

    if(calc(n, x, y) == false){

        ans[arr[x][y]]++;

        return;

    }

    for(int i=x; i<x+n; i+=(n/2)){

        for(int j=y; j<y+n; j+=(n/2)){

           cal(n/2, i, j);

        }

    }

}

int main() {

    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 >> arr[i][j];

        }

    }

    cal(N, 0, 0);

    for(int i=0; i<2; i++){

        cout << ans[i] << '\n';

    }

}