<백준> 15788번 밸런스 스톤 (IUPC)

2018 인하대학교 프로그래밍 경진대회(IUPC) I번 문제

문제

우주의 인구를 반으로 줄이려는 악당 타노진스는 우주의 인구 수를 조절할 수 있는 밸런스 스톤이라는 보석을 차지하려고 한다. 이에 맞서는 씨벤저스 멤버 캡틴 학규는 타노진스보다 먼저 밸런스 스톤을 발견하여 파괴하려고 한다.

밸런스 스톤은 N × N 블록으로 이루어진 숫자 퍼즐을 완성하면 얻을 수 있다. 이 숫자 퍼즐은 1가지 블록의 수가 비어져 있는 상태이며, 규칙을 만족하는 수 M을 블록에 채워넣으면 퍼즐이 완성된다. 규칙은 다음과 같다.

[ 규칙 ]

1. M을 채워넣었을 때 같은 행에 있는 수의 합은 모두 같아야 한다.
2. M을 채워넣었을 때 같은 열에 있는 수의 합은 모두 같아야 한다.
3. M을 채워넣었을 때 블록의 대각선의 있는 수들의 합도 모두 같아야 한다.
4. 규칙 1, 2, 3의 합은 모두 같아야 한다.
5. 어떠한 수를 M에 넣어도 규칙 1, 2, 3을 만족하지 못한다면 -1을 블록에 채워 넣으면 블록이 완성된다.

캡틴 학규를 도와 퍼즐을 완성하고 우주의 평화를 지키자

입력

입력의 첫째 줄에 맵의 크기 N(2 ≤ N ≤ 500)이 주어진다. 다음 N줄에 각 블록의 수 k가 N개가 주어진다. (1 ≤ k ≤ 1,000,000,000의 자연수), 비어있는 블록은 수 0으로 주어지며 조건을 만족하는 수 M이 존재할 시 무조건 자연수 값이 되도록 주어진다.

출력

퍼즐의 조건을 만족하는 수 M을 출력한다.

문제 풀이

규칙 1,2,3 중 하나를 사용하여 M의 값을 맞춘다. N >= 2 이고 비어있는 블록은 하나임으로 항상 M을 구할 수 있다. 그 이후 M값을 블록에 집어넣고 규칙을 만족하는지 검사한다.

1. 규칙 1을 이용하여 M값을 구한다

2. M을 matrix에 넣고 규칙 모두가 만족하는지 검사한다.

3. 이떄 M은 항상 자연수여야 하며 알맞는 M이 존재하지 않으면 -1 을 출력한다.

C++

#include <iostream>
using namespace std;
 
long long int matrix[502][502];
 
long long int rowSum (int i, int N){    //행 더하기
    long long int sum=0;
    for(int j =0; j<N; j++){
            sum += matrix[i][j];
        }
    return sum;
}
 
long long int columnSum (int j, int N){        //열 더하기
    long long int sum=0;
        for(int i =0; i<N; i++){
            sum += matrix[i][j];
        }
    return sum;
}
 
void noAnswer(){    
    cout<<"-1"<<endl;
    exit(0);
}
 
int main() {
    int N, emptyX, emptyY;
    long long int temp, M;
    long long int sum=0;
    long long int Msum=0;
    long long int digonalSum[2] = {0,};
    cin >> N;
    
    for(int i=0; i<N; i++){
        for(int j=0; j<N;j++){
            scanf("%d",&temp);
            if(temp == 0){
                emptyX=i;
                emptyY=j;
            }
            matrix[i][j] = temp;
        }
    }
    
    if(emptyX != 1){        //규칙 1로 일단 M을 임시로 맞추어 놓는다.
        sum = rowSum(1,N);
    }else{
        sum = rowSum(0,N);
    }
    
    Msum = rowSum(emptyX,N);
    
    M = sum - Msum;
    
    if(1>M){        //M은 자연수이여야 하므로 0이거나 음수면 종료한다.
        noAnswer();
    }
    
    matrix[emptyX][emptyY] = M;
    
    for(int i=0;i<N;i++){        //규칙 1, 2 (가로,세로) 확인
        if(sum != rowSum(i,N)||sum != columnSum(i,N)){
            noAnswer();
        }
        digonalSum[0]+=matrix[i][i];
        digonalSum[1]+=matrix[i][N-i-1];
    }
    
    M=(digonalSum[0]==sum && digonalSum[1] == sum) ? M : -1;    //규칙 3 (대각선) 확인
    
    cout<<M<<endl;
}