문제

문제 2052

행렬 최소합

시간 제한 1.000초 메모리 제한 128MB

문제 설명

3X3 크기의 행렬이 주어졌을 때 각 행과 열이 중복되지 않도록 선택하여 그 합의 최소값을 구하여라
예를 들어 다음과 같은 행렬을 생각해보자.
[[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개의 열 데이터가 공백으로 구분되어 입력된다.

출력 설명

최소값을 출력한다.

입력 예시

1 5 3
2 5 7
5 3 5

출력 예시

8

출처

등록된 출처가 없습니다.