[BaekJoon] 삼성 sw 역량 테스트(게리멘더링2)

• 이 문제는 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int total=0;
int arr[30][30];
int temp[30][30];
int n;
int y1,x1,y2,x2,y3,x3;

bool inside(int y,int x){
    return 1<=y && y<=n && 1<=x && x<=n;
}

int get_region(int y,int x,int dy1,int dx1,int dy2,int dx2,int dy3,int dx3){
    
    vector<int> sum(5);
    y1=dy1,x1=dx1,y2=dy2,x2=dx2,y3=dy3,x3=dx3;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            temp[i][j]=0;
        }
    }
    
    for(int i=1;i<y;i++){
        for(int j=1;j<=x;j++){
            sum[0]+=arr[i][j];
            temp[i][j]=1;
        }
    }
    int cnt=0;
    for(int i=y;i<dy1;i++){
        cnt++;
        for(int j=1;j<=x-cnt;j++){
            sum[0]+=arr[i][j];
            temp[i][j]=1;
        }
    }
    
    for(int i=1;i<y;i++){
        for(int j=x+1;j<=n;j++){
            sum[1]+=arr[i][j];
            temp[i][j]=2;
        }
    }
    
    cnt=0;
    for(int i=y;i<=dy2;i++){
        cnt++;
        for(int j=x+cnt;j<=n;j++){
            sum[1]+=arr[i][j];
            temp[i][j]=2;
        }
    }
    
    cnt=0;
    for(int i=dy1;i<=dy3;i++){
        for(int j=1;j<dx1+cnt;j++){
            sum[2]+=arr[i][j];
            temp[i][j]=3;
        }
        cnt++;
    }
    
    for(int i=dy3+1;i<=n;i++){
        for(int j=1;j<dx3;j++){
            sum[2]+=arr[i][j];
            temp[i][j]=3;
        }
    }
    
    cnt=0;
    for(int i=dy2+1;i<=dy3;i++){
        for(int j=n;j>=dx2-cnt;j--){
            sum[3]+=arr[i][j];
            temp[i][j]=4;
        }
        cnt++;
    }
    
    for(int i=dy3+1;i<=n;i++){
        for(int j=dx3;j<=n;j++){
            sum[3]+=arr[i][j];
            temp[i][j]=4;
        }
    }
    
    sum[4]=total-sum[0]-sum[1]-sum[2]-sum[3];
    sort(sum.begin(),sum.end());
    return sum[4]-sum[0];
}

// 첫 좌표를 기준으로 -1 기울기에 해당하는 좌표 탐색 후 1 기울기에 해당하는 좌표 탐색
// 두 좌표로 세 번째 좌표도 나타낼 수 있다 => 중앙값 정리
int getresult(int y,int x){
    int result=987987987;
    
    for(int i=1;i<=n;i++){
        int dy1=y+i;
        int dx1=x-i;
        
        if(inside(dy1,dx1)){
            for(int j=1;j<=n;j++){
                
                int dy2=y+j;
                int dx2=x+j;
                if(inside(dy2,dx2)){
                    int dy3=dy1+dy2-y;
                    int dx3=dx1+dx2-x;
                    if(inside(dy3,dx3)){
                        int sum=get_region(y,x,dy1,dx1,dy2,dx2,dy3,dx3);
                        if(result>sum){result=sum;}
                    }
                }

                else{break;}
            }
            
        }
        else{break;}
    }
    return result;
}

int main(){
    int min=987987987;
    cin>>n;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>arr[i][j];
            total+=arr[i][j];
        }
    }
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int sum=getresult(i,j);
            if(min>sum){
                min=sum;
            }
        }
    }
    cout<<min;
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.