Move Stone

면접 대비

시간 제한1초메모리 제한2048 MB

요약
n x n 격자에 총 n^2개의 돌이 있을 때, 같은 행이나 열로 돌을 옮겨 각 칸에 돌을 하나씩 두는데 필요한 최소 이동 횟수를 구한다.
난이도

보통10점 중 5점

유형
그리디, 정렬, 수학, 구현
정답자
아직 제출이 없습니다

문제

You are given an n×nn \times n grid. Each cell initially contains some number of stones, such that the total number of stones is exactly n2n^2.

In one move, you may take a single stone and move it to any other cell in the same row or the same column.

Your goal is to minimize the number of moves needed to make each cell contain exactly one stone.

입력

The first line contains an integer nn, representing the size of the grid.

Followed by nn lines, the ii-th of which contains nn integers, the jj-th integer a_i,ja\_{i,j} represents the number of stones in cell (i,j)(i, j).

출력

Output a single integer, the minimum number of moves required to make each cell contain exactly one stone.

제한

  • 1≤n≤5001 ≤ n ≤ 500
  • 0≤a_i,j≤n20 ≤ a\_{i,j} ≤ n^2
  • The initial number of stones is exactly equal to the number of cells on the board.

예제2

  1. 예제 1

    입력
    3
0 1 2
0 2 2
1 1 0
    예상 출력
    3

  2. 예제 2

    입력
    5
1 2 4 0 1
2 0 0 2 0
1 4 1 0 1
2 0 0 0 0
1 2 0 1 0
    예상 출력
    11