백준 1780 종이의 개수 - 분할정복 - C++

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

1780번: 종이의 개수

전형적인 분할정복 알고리즘이다.

n*n짜리 배열에서 같은 숫자가 나오면 패스고,

다른 숫자가 검출이 되면 n/3*n/3짜리 배열 9개로 쪼개서 재귀함수를 돌려서 진행하면 된다.

 

이론상 다맞아보였는데 기본적인 곳에서 실수한게,

예를들어서 18번째줄에

dx/3을 하면 3을 나눈 몫으로 정확히 계산이 되는데

(1/3)*dx 로 계산을 하면 dx가 어떤 값이 들어가도 0이 나오는 현상을 발견했다.

 

내가 c++에 익숙하지 않은 탓이었다.. 파이썬만 하도 쓰다 c++로 넘어오다보니까 ㅠㅠ

다음부턴 조심하도록 하자.

 

#include <iostream>
using namespace std;
int n;
int arr[2187][2187];
int count_m1=0,count_0=0,count_1 =0;
 
void returnnum(int sx, int ex, int sy, int ey){
    int rn=arr[sx][sy];
    int dx=ex-sx;
    int dy=ey-sy;
//    cout<<"what is running is returnnum "<<sx<<" "<<ex<<" "<<sy<<" "<<ey<<"\n";
    for(int i=sx; i<ex; i++){
        for(int j=sy; j<ey; j++){
            int temp=arr[i][j];
            if(rn!=temp){
//                cout<<rn<<" "<<"and"<<temp<<"is different!\n";
//                cout<<"dx is "<<dx/3<<" and dy is "<<2/3*dy<<"\n";
                returnnum(sx,sx+dx/3,sy,sy+dy/3);
                returnnum(sx,sx+dx/3,sy+dy/3,sy+dy*2/3);
                returnnum(sx,sx+dx/3,sy+dy*2/3,sy+dy);
                returnnum(sx+dx/3,sx+dx*2/3,sy,sy+dy/3);
                returnnum(sx+dx/3,sx+dx*2/3,sy+dy/3,sy+dy*2/3);
                returnnum(sx+dx/3,sx+dx*2/3,sy+dy*2/3,sy+dy);
                returnnum(sx+dx*2/3,sx+dx,sy,sy+dy/3);
                returnnum(sx+dx*2/3,sx+dx,sy+dy/3,sy+dy*2/3);
                returnnum(sx+dx*2/3,sx+dx,sy+dy*2/3,sy+dy);
                return;
 
            }
//            cout<<temp;
        }
    }
    if(rn==-1)
        count_m1++;
    else if (rn==0)
        count_0++;
    else if (rn==1)
        count_1++;
}
 
int main(void){
    ios_base::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];
        }
    }
    returnnum(0,n,0,n);
//    returnnum(6,9,6,9);
    cout<<count_m1<<endl;
    cout<<count_0<<endl;
    cout<<count_1<<endl;
 
}