문제 설명
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이 되어 최소가 된다.
입력 설명
3X3 크기의 행렬 데이터가 3줄에 걸쳐 입력된다.
각 줄에는 3개의 열 데이터가 공백으로 구분되어 입력된다.
각 줄에는 3개의 열 데이터가 공백으로 구분되어 입력된다.
출력 설명
최소값을 출력한다.
입력 예시 Copy
1 5 3
2 5 7
5 3 5
출력 예시 Copy
8