조화행렬 > 문제은행



문제은행

3236 : 조화행렬

제한시간: 5Sec    메모리제한: 768mb
해결횟수: 0회    시도횟수: 0회    채점준비중입니다.



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

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

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

 

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

 

5321aa34e52c55673fbbb84628c752ab_1532762
 

 

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

 

 5321aa34e52c55673fbbb84628c752ab_1532762 

 

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

행렬 Rx행 열 원소 Rx​[i, j] 는 행렬 X열의 원소 X[i, j]가 X i번째 행에서 

몇 등(가장 큰 수가 1등)인지 나타낸다. 

의 등수 행렬 Rx는 다음과 같다. 

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

 

5321aa34e52c55673fbbb84628c752ab_1532762
 

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

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

 

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

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

 

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


5321aa34e52c55673fbbb84628c752ab_1532763


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

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


2 × N 또는 3×N 행렬 Q가 주어졌을때, Q의 조화로운 열-부분행렬 중

가장 큰 행렬의 열 개수를 구하는 프로그램을 작성하시오.


소스파일의 이름은 matrix.c 또는 matrix.cpp를 권장하지만, 서버에 제출하는 데는 다른 이름도 상관없다.

 

 

 

 


표준 입력으로 행의 개수 M 과 열의 개수 N 이 첫 줄에 입력된다. 
다음 M개의 줄에 각 행의 정보가 한 줄에 하나씩 입력된다. 
한 줄에는 한 행의 원소를 나타내는 N 개의 양의 정수가 열순서대로 공백을 사이에 두고 주어진다.


조화로운 열-부분행렬 중 가장 큰 행렬의 열 개수를 나타내는 정수를 표준 출력으로 출력한다.

 [부분문제의 제약 조건] 
모든 부분문제에서 행렬의 원소는 1 이상 109 이하이다.
* 부분문제 1: 전체 점수 100점 중 14점에 해당하며 M = 2, 3 ≤ N ≤ 10,000 이다.
* 부분문제 2: 전체 점수 100점 중 9점에 해당하며 M = 3, 3 ≤ N ≤ 10,000 이다.
* 부분문제 3: 전체 점수 100점 중 15점에 해당하며 M = 2, 3 ≤ N ≤ 200,000 이다.
* 부분문제 4: 전체 점수 100점 중 62점에 해당하며 M = 3, 3 ≤ N ≤ 200,000 이다.

[Copy]
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
[Copy]
4


[Copy]
2 9
10 74 41 15 89 52 16 63 75
30 53 22 33 46 45 25 47 21
[Copy]
5






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