Problem1309--행렬의 곱 - VERY HARD

1309: 행렬의 곱 - VERY HARD

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 58  Solved: 18
[Submit] [Status] [Web Board] [Creator:]

Description

MxK 행렬인 A와 KxN 행렬인 B 2개가 주어졌을 때 두 행렬의 곱인 A * B인 행렬 C 를 구하는 문제이다.
이때 행렬의 곱이므로, MxN 크기의 행렬이다.
조건은 아래와 같다.
1.  M, N, K 의 크기는 1200으로 고정이며, 시간은 1초이다.
2. 1200x1200의 크기를 단순 연산을 한다면 1,728,000,000번 연산이 필요하다.
3. 해당 문제는 메모리의 최적화가 필요 없을 정도로 매우 큰 메모리가 할당이 된다. 
4. 모든 입출력은 short(2바이트) 형이다. (이때, 출력 값은 오버플로우, 언더플로우는 발생하지 않는다.)
5. 모든 방법(해킹, 파일 입출력, GPU 가속)을 사용해도 된다.
6. 테스트 케이스는 하나이다.

Input

첫번째 줄 이하 부터는 행렬의 값이 들어온다.
M, N, K의 값은 1200 이다.
각 행렬의 요소는 short 타입으로 들어온다.

Output

두 행렬의 곱한 결과를 출력한다.

Sample Input Copy

1 2 3  ...
5 6 7  ...
9 10 11 ...
... ... ... ...
12 13 14 ...
15 16 17 ... 
18 19 20 ...
... ... ... ...

Sample Output Copy

곱한 결과. 출력 예시는 1308번 문제를 참고한다.

HINT

학과 동아리 412호에 언제든지 찾아오면 차차가 기다리고 있습니다.
언제든지 오셔도 괜찮습니다. 

학과 동아리 단톡방에서 어떻게 푸는지 물어보시면 친절하게 답변을 해드립니다.
한가지 문제에 대한 함정이 있다면, 차차가 PoC를 하고 문제를 만드는데 4~5시간 이상이 걸렸다는 것이다.
만약 문제를 푸셨다면, 제가 근사한 밥 한끼 사겠습니다.

Source/Category