[백준/분할정복/C++] 1780번 종이의 개수

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

1780번: 종이의 개수

분할정복을 이용하여 풀면 된다

주의할 점

• 모두 같은 수인지 체크하는 check함수에서  for 문 돌릴때 mapp[x+i][y+j] 확인
• divide 함수에서 for문 돌릴때 전체 n이 아니라 나누어진 수 만큼만 돌리면 됨

#include <bits/stdc++.h>

using namespace std;

int n;
int result[3]; // [0]:-1종이개수, [1]:0종이 개수, [2]:1종이 개수
int mapp[2200][2200];

bool check(int x, int y, int n){
    int pivot = mapp[x][y];

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(mapp[x+i][y+j] != pivot)
                return false;
        }
    }
    return true;
}

void divide(int x, int y, int n){
    // 다 같은 경우
    if(check(x, y, n)){
        result[mapp[x][y]+1]++;
        return;
    }

    int div = n/3;

    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            divide(x+div*i, y+div*j, div);
        }
    }
}

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 >> mapp[i][j];
        }
    }
    divide(0, 0, n);

    for(int i : result){
        cout << i << '\n';
    }

    return 0;
}

비슷한 문제

https://develop-me-z.tistory.com/128

 

참고

https://algosu.tistory.com/86