술탄의 후계자들
면접 대비시간 제한1초메모리 제한128 MB
8x8 체스판마다 서로 공격하지 않는 퀸 8개를 놓아 차지한 칸에 적힌 수의 합이 최대가 되도록 한다.
문제
누비아의 술탄에게는 자식이 없어서, 자신이 죽으면 나라를 최대 개의 지역으로 나누어 각 지역을 어떤 시험에서 가장 뛰어난 성적을 낸 사람에게 물려주기로 했다. 한 사람이 둘 이상의 지역을, 심지어 모든 지역을 물려받을 수도 있다.
지혜로운 사람만이 후계자가 되도록, 술탄은 다음과 같은 시험을 고안했다. 큰 홀 안에 개의 체스판을 놓는다. 각 체스판은 격자이며, 모든 칸에는 부터 까지의 수가 하나씩 적혀 있고, 개의 퀸이 함께 주어진다. 각 지원자는 어떤 퀸도 다른 퀸을 위협하지 않도록 개의 퀸을 판 위에 놓아야 하며, 선택된 칸에 적힌 수들의 합이 술탄이 미리 정한 값 이상이 되도록 해야 한다.
(체스 규칙에 따르면, 이는 각 행과 각 열에 정확히 하나의 퀸이 있고, 각 대각선에는 퀸이 최대 하나만 있어야 함을 의미한다.)
각 체스판에 대해, 서로 위협하지 않는 개의 퀸을 놓아 얻을 수 있는 수들의 합의 최댓값을 구하는 프로그램을 작성하여라. (술탄은 뛰어난 체스 기사이자 훌륭한 수학자이므로, 그녀가 정한 점수는 얻을 수 있는 최댓값이다.)
입력
첫째 줄에 체스판의 개수 가 주어진다 (). 이어서 개의 체스판이 주어진다. 각 체스판은 개의 줄에 각각 개의 정수가 적힌 형태, 즉 총 개의 수로 주어지며, 각 수는 보다 작은 양의 정수이다.
출력
각 체스판에 대해 얻을 수 있는 최대 점수를 한 줄에 하나씩 출력한다. 각 점수는 너비 의 칸에 오른쪽 정렬하여 출력한다.