[백준/C++] 1780번 종이의 개수

문제: www.acmicpc.net/problem/1780

1780번: 종이의 개수

 

 

문제풀이

 

기준점 x, y와 종이의 변의 길이 N을 매개변수로 하는 함수를 선언하여 재귀방식으로 문제를 해결했다.

 

기준점과 종이의 나머지 부분을 비교하여 같으면 카운트를 하고 다르면 기준점과 N를 적절하게 나누어 9개의 함수를 호출했다. (9등분) 

 

 

코드

#include <iostream>

using namespace std;

int cntm1 = 0; //-1인 종이 갯수
int cnt0 = 0; //0 종이 갯수
int cnt1 = 0; //1 종이 갯수
int arr[2187][2187]; //N은 3^7보다 작거나 같다.

void func(int x, int y, int N){
    bool flag = true; //종이가 같은 숫자로 채워져있는지 여부

    for(int i=x; i<x+N; i++){
        for(int j=y; j<y+N; j++){
            if(arr[x][y] != arr[i][j]) //기준점과 나머지 부분을 비교
                flag = false;
        }
    }

    if(flag){ //같은 숫자로 채워져있으면
        if(arr[x][y] == -1) //해당 종이 카운트
            cntm1++;
        else if(arr[x][y] == 0)
            cnt0++;
        else
            cnt1++;
    }
    else{ //같은 숫자로 채워져있지 않으면
        N /= 3;
        func(x, y, N);
        func(x+N, y, N);
        func(x+N*2, y, N);
        func(x, y+N, N);
        func(x, y+N*2, N);
        func(x+N, y+N, N);
        func(x+N*2, y+N, N);
        func(x+N, y+N*2, N);
        func(x+N*2, y+N*2, N);
    }

}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int N;
    cin>>N;

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            int num;
            cin>>num;
            arr[i][j] = num;
        }
    }

    func(0, 0, N);

    cout<<cntm1<<"\n";
    cout<<cnt0<<"\n";
    cout<<cnt1<<"\n";

    return 0;
}

 

 

결과