격자판 > 문제은행



실전대비 Level6

1512 : 격자판

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 34 회    시도횟수: 111 회    Special Judge



N개의 행과 M개의 열로 구성된 격자판의 각 칸에 숫자들이 들어있다. 

정수 K(K≥2)가 주어진다. K는 N보다 작고, M보다도 작다. 

격자판에서 R개의 행과 C개의 열을 R+C=K가 만족하도록 선택하고, 

선택된 행과 열을 제외한 나머지 칸에 있는 숫자들 가운데 가장 큰 숫자가 최소가 되도록 하려고 한다.

N=4, M=5인 경우의 격자판의 예가 다음 그림과 같이 주어졌다고 하자.

  e3050b66a1b29a01767400d7560a4131_1449746

 

위의 예에서 K=3인 경우, 1행, 3행과 4열을 선택하면 다음 그림과 같이 선택된 행과 열을 제외한 나머지 칸에 있는 숫자들 가운데 제일 큰 숫자는 5이다.

 

e3050b66a1b29a01767400d7560a4131_1449746
 

 

3행, 3열과 4열을 선택하여도 선택된 행과 열을 제외한 나머지 칸 가운데 제일 큰 숫자는 5이다. 

그러나 달리 선택하여 나머지 칸에 있는 숫자들이 모두 5보다 작게 만들 수는 없다.

 

숫자들이 들어있는 격자판과 선택할 수 있는 행의 개수와 열의 개수의 합이 주어졌을 때, 

선택한 행과 열을 제외한 나머지 칸에 있는 숫자들 가운데 가장 큰 숫자가 최소가 되도록 행과 열을 선택하기 위한 프로그램을 작성하시오.

 

부분 점수는 없다.

 




첫 줄에는 격자판의 크기를 나타내는 정수 N과 M이 주어진다. N과 M은 3이상이며, 300이하인 정수이다. 
둘째 줄에는 선택할 수 있는 행과 열의 개수의 합 K(K<N, K<M)가 주어진다. 
셋째 줄부터 격자판에 들어있는 양의 정수들이 한 줄에 한 행씩 1행부터 차례대로 주어진다. 
격자판에 들어있는 각 숫자는 1 이상 500,000 이하의 정수이다. 같은 줄에 입력되는 각 정수들 사이에는 한 개의 공백이 있다.



첫 번째 줄에 R + C = K를 만족하는 R개의 행과 C개의 열을 선택하여, 
선택된 행과 열을 제외한 나머지 칸에 있는 숫자들 가운데 가장 큰 숫자의 최소값을 출력한다. 
둘째 줄에는 선택한 행의 개수와 이어서 행 번호를 오름차순으로 출력한다. 
셋째 줄에는 선택한 열의 개수와 이어서 열 번호를 오름차순으로 출력한다. 
행의 개수나 열의 개수가 0인 경우에는 해당하는 줄에 0만 출력한다. 같은 줄에 출력되는 각 정수들 사이에는 한 개의 공백을 둔다.

조건을 만족하는 답이 여러 개인 경우에는 그 중에서 하나만 출력하면 된다.


4 5 
3
3 1 7 6 3
3 4 2 8 2
8 6 4 2 4
3 5 1 2 1
5
2 1 3
1 4





bipartite matching

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.