문제 설명
3X3 크기의 행렬이 주어졌을 때 각 행과 열이 중복되지 않도록 선택하여 그 합의 최소값을 구하여라
예를 들어 다음과 같은 행렬을 생각해보자.
[[1 5 3]
[2 5 7]
[5 3 5]]
각 행과 열이 중복되지 않도록 선택하는 것은 첫 번째 행에서 1을 선택한 경우, 2번째 행에서는 2를 선택할 수 없고 5,7 중 하나를 선택하여야 한다. 또한 2번째 행에서 7을 선택한 경우 마지막 행에서는 3을 선택해야 한다.
이 경우 합이 11이 된다.
하지만 첫 번째 행에서 3, 두번 째 행에서 2, 세번째 행에서 3을 선택하면 합이 8이 되어 최소가 된다.
예를 들어 다음과 같은 행렬을 생각해보자.
[[1 5 3]
[2 5 7]
[5 3 5]]
각 행과 열이 중복되지 않도록 선택하는 것은 첫 번째 행에서 1을 선택한 경우, 2번째 행에서는 2를 선택할 수 없고 5,7 중 하나를 선택하여야 한다. 또한 2번째 행에서 7을 선택한 경우 마지막 행에서는 3을 선택해야 한다.
이 경우 합이 11이 된다.
하지만 첫 번째 행에서 3, 두번 째 행에서 2, 세번째 행에서 3을 선택하면 합이 8이 되어 최소가 된다.
입력 설명
첫번째 줄에는 행렬의 크기 N이 입력된다.
(단, \((1 \le N \le 22)\)
NXN 크기의 행렬 데이터가 N줄에 걸쳐 입력된다.
각 줄에는 N개의 열 데이터가 공백으로 구분되어 입력된다.
(단, \((1 \le N \le 22)\)
NXN 크기의 행렬 데이터가 N줄에 걸쳐 입력된다.
각 줄에는 N개의 열 데이터가 공백으로 구분되어 입력된다.
출력 설명
최소합이 출력한다.
입력 예시 Copy
3
1 2 3
4 5 6
7 8 9
출력 예시 Copy
15