글 읽기 - 분할 정복

johyesong8686 3년 전 0

분할 정복 문제 인데 ㅜㅜ 구글링 한 코드랑 논리가 같은 걸로 보이는데

if(arr[x][y]!=arr[i][j]) 이부분에서 모두 false 처리 되어서

size가 1일때 까지 분할되더라구요 ..

왜 각 0,1,-1,개의 숫자 값이 출력되는 지 모르겠습니다 ㅜㅜ

어떤 논리가 잘못되었을까요

#include <iostream>
using namespace std;

int n;
int arr[3000][3001];
int num[3];

void div_num(int x,int y,int size){
    bool finish=true;
    //기저일 경우 빼준다 
    if(size==1){
        
        num[arr[x][y]+1]++;
        
        return;

    }
   
    for(int i=x; i<x+n;i++){
        for(int j=y; j<y+n;j++){
            if(arr[x][y]!=arr[i][j]){
                //cout <<"set:" <<x <<" , "<<y <<" :"<<arr[x][y]<< '\n';

                //cout <<"x: "<<i <<" y: "<<j<<'\n';
                //cout <<"size : "<<size << ", "<<arr[i][j] <<'\n';
                finish=false;
                break;

            }

        }
        if(!finish){
            break;
        }
    }
    

    if(finish){
        //cout <<"x: "<<x <<" y: "<<y <<'\n';
        //cout <<"size : "<<size << ", "<<arr[x][y] <<'\n';
        num[arr[x][y]+1]++;

        return ;
    }else{
        int di=size/3;
        for(int i=0; i<3;i++){

            for(int j=0; j<3;j++){
                div_num(x+i*di,y+j*di,di);
            }
        }
        
        return;
        



    }


}

int main(void ){

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

    }
    div_num(0,0,n);

    cout <<num[0]<<'\n' <<num[1]<<'\n'<<num[2]<<'\n';



    return 0;
}

johyesong8686 3년 전 0

지역변수와 전역변수를 잘못 작성했습니다 ㅜ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

분할 정복

johyesong8686 3년 전 0

johyesong8686 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말