레이팅 미적용서로 다른 양의 정수로 구성된 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와 이의 등수행렬 \(R_{Y}\)이다.
등수행렬 \(R_{Y}\)의 모든 행이 일치하므로 열-부분행렬 Y는 조화로운 행렬이다. 행렬 Q의 조화로운 열-부분행렬 중 가장 큰 행렬의 크기는 3×4이다.
2×N 또는 3×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번