레이팅 미적용서로 다른 양의 정수로 구성된 \(2 \times N\) 또는 \(3 \times 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\)와 이의 등수행렬 \(R_{Y}\)이다.
등수행렬 \(R_{Y}\)의 모든 행이 일치하므로 열-부분행렬 \(Y\)는 조화로운 행렬이다. 행렬 \(Q\)의 조화로운 열-부분행렬 중 가장 큰 행렬의 크기는 \(3 \times 4\)이다.
\(2 \times N\) 또는 \(3 \times N\) 행렬 \(Q\)가 주어졌을 때, \(Q\)의 조화로운 열-부분행렬 중 가장 큰 행렬의 열 개수를 구하는 프로그램을 작성하시오.
표준 입력으로 행의 개수 \(M\)과 열의 개수 \(N\)이 첫 줄에 입력된다. 다음 \(M\)개의 줄에 각 행의 정보가 한 줄에 하나씩 입력된다. 한 줄에는 한 행의 원소를 나타내는 \(N\)개의 양의 정수가 열 순서대로 공백을 사이에 두고 주어진다.
조화로운 열-부분행렬 중 가장 큰 행렬의 열 개수를 나타내는 정수를 표준 출력으로 출력한다.
3 9
10 74 41 15 89 52 16 63 75
30 53 22 33 46 45 25 47 21
29 49 13 26 59 17 62 34 19
4
2 9
10 74 41 15 89 52 16 63 75
30 53 22 33 46 45 25 47 21
5
생성자가 기록되지 않았습니다.
출처 올림피아드 > 한국정보올림피아드 > KOI 2018 > 2차 대회 > 고등부 2번