출처
Codeforces
(http://codeforces.com/problemset/problem/711/B)
문제이해
빈 칸을 의미하는 0이 한 개만 포함되는 불완전한 마방진이 입력으로 주어진다.
가로, 세로, 대각선의 합이 같은 마방진을 성립하게 하려면 어떤 수를 0 자리에 채워 넣어야 하는지 구하는 문제이다.
채워 넣을 수는 양의 정수로 한정된다. 채워 넣을 양의 정수가 없다면 -1을 출력하고, 있다면 그 수를 출력해야 한다.
문제접근
각각의 행 합, 열 합, 대각선 합을 구해서
합이 다른 것을 찾는데, 그 행이나 열에는 0이 들어있어야 한다.
코드포시스 라운드에 참가할 때
7 0 5
2 4 6
3 8 1
이런식으로 빈 칸에 0을 채워야 될 경우 -1을 출력해야 하는데
0을 출력해서 계속 W/A가 떴었다..
먼저 0이 들어있는 위치를 구하고,
0이 들어있지 않은 각각의 모든 행과 열들의 합을 구해서 합이 모두 같은지 검사한다.
그리고 그 합들이 모두 같고, 0이 포함되어있는 행/열보다 크면 유효하다고 판단한다.
대각선 2개도 고려해야 한다.
구현
printf() 함수로 64비트 정수를 출력할 때 서식문자로 %lld 대신 %I64d를 써서 제출.
코드
https://github.com/tibyte/algorithm-problems/blob/master/codeforces/711b.cpp