아주대 2000년 정보올림피아드- 건물 세우기 > 문제은행 : 정보올림피아드&알고리즘



1249 : 건물 세우기

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
17 회   
시도횟수
68 회   

문제

(주)정올에서는 여러 개의 빌딩을 새로 지을 계획이다. 그래서 빌딩을 세울 장소를 선정하였다. 

그리고 각 빌딩을 각 장소에 세울 경우에 드는 비용을 추정하였다. 예를 들어서 아래의 표를 보자


  1 2 3

A 4 7 3

B 2 6 1

C 3 9 4

A, B, C 는 건물을 나타내고, 1, 2, 3은 장소를 나타낸다. 
예를 들어서 건물 B를 장소 1에 세우면 비용이 2가 들고, 장소 2에 세우면 비용이 6, 장소 3에 세우면 비용이 1만큼 든다. 
물론 한 장소에는 한 건물밖에 세울 수 없다. 만일 A를 장소 2에, B를 장소 3에, C를 1에 세우면 전체 비용이 7+1+3 = 11이 필요하다. 
그런데 A를 3, B를 1, C를 2에 세우면 3+2+9 = 14 가 필요하다.


각 빌딩을 어느 장소에 세우면 비용의 합이 최소가 되는지 구하는 프로그램을 작성하시오.


입력형식

입력 파일의 첫 줄은 빌딩의 개수 n(1≤n≤20)이 들어있다. 

그 다음 n 줄에는 각 건물을 각 장소에 세울 경우에 드는 비용이 입력된다.

물론 각 줄 에는 n개의 수가 입력된다. 비용을 나타내는 수의 범위는 1이상 100미만이다.


출력형식

첫 줄에는 최소비용을 출력한다.

둘째 줄에는 건물을 세울 장소들을 알파벳 순서에 따라 빈칸을 하나씩 두고 출력한다.


입력 예

4
11 12 18 40
14 15 13 22
11 17 19 23
17 14 20 28

출력 예

61
1 3 4 2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP