문제 설명
주어진 \(n \times n\) 행렬에서 \(n\)개의 원소를 행과 열이 중복되지 않도록 선택할 때 얻을 수 있는 최소합을 구해보자.
다음은 \(n\)이 3일 때의 행렬의 예시이다.
\( \begin{bmatrix} 1 & 5 & 3 \\ 2 & 4 & 7 \\ 5 & 3 & 5 \end{bmatrix} \)
이 경우 (1,3), (2,1), (3,2)의 원소합인 3+2+3=8이 최소합이된다.
다음은 \(n\)이 3일 때의 행렬의 예시이다.
\( \begin{bmatrix} 1 & 5 & 3 \\ 2 & 4 & 7 \\ 5 & 3 & 5 \end{bmatrix} \)
이 경우 (1,3), (2,1), (3,2)의 원소합인 3+2+3=8이 최소합이된다.
입력 설명
첫 번째 줄에 행렬의 크기 \(n\)이 입력된다.
두 번째 줄부터 \(n+1\)번째 줄까지 각 행 데이터 \(n\)개가 공백으로 구분되어 입력된다.
두 번째 줄부터 \(n+1\)번째 줄까지 각 행 데이터 \(n\)개가 공백으로 구분되어 입력된다.
출력 설명
행과 열이 중복되지 않도록 선택된 요소의 최소합이 출력된다.
입력 예시 Copy
3
1 5 3
2 4 7
5 3 5
출력 예시 Copy
8