서로 다른 양의 정수로 구성된 2 × N 또는 3 × N 행렬(이차원 배열)을 고려하자.

어떤 행렬 Q가 주어졌을 때, 1개 이상의 열을 선택하여 순서대로 붙여만든 행렬을 Q의 열-부분행렬이라 한다.

(Q도 자신의 열-부분행렬이다.)

예를 들어, 행렬 Q가 다음과 같이 주어졌을 때,

다음 행렬 X 는 Q 에서 2열, 3열, 5열, 6열, 8열을 선택하여 만든 열-부분행렬이다.

행렬 X의 등수행렬 R_x를 다음과 같이 정의하자.

행렬 R_x의 i 행 j 열 원소 R_x[i, j] 는 행렬 X의 i 행 j 열의 원소 X[i, j]가 X 의 i번째 행에서 몇 등(가장 큰 수가 1등)인지 나타낸다.

X 의 등수 행렬 R_x는 다음과 같다.

(원본 행렬 Q의 원소는 모두 다르므로, R_x의 각 행에서 같은 등수는 존재하지 않는다.)

X[1, 1]에 저장된 74는 X의 1행 원소들 74, 41, 89, 52, 63 중에서 두 번째로 크므로 R_x[1, 1] 에 2가 저장된다.

다른 원소 값도 비슷하게 계산된다.

어떤 열-부분행렬의 등수행렬에서 모든 행이 일치하면, 그 열-부분행렬을 조화로운 행렬이라고 한다.

R_x의 경우, 1행과 3행은 일치하나, 2행은 다른 행과 일치하지 않으므로 조화로운 행렬이 아니다.

다음은 행렬 Q 에서 2열, 3열, 6열, 8열을 선택하여 만든 열-부분행렬 Y와 이의 등수행렬 Ry 이다.

등수행렬 Ry 의 모든 행이 일치하므로 열-부분행렬 Y 는 조화로운 행렬이다.

행렬 Q의 조화로운 열-부분행렬 중 가장 큰 행렬의 크기는 3×4이다.

2 × N 또는 3×N 행렬 Q가 주어졌을때, Q의 조화로운 열-부분행렬 중 가장 큰 행렬의 열 개수를 구하는 프로그램을 작성하시오.

조화행렬 timer 5000초 memory 768MB

조화행렬 5000초 768MB