문제 출제 및 검수: 한상덕(leo.han)
이 문제로 영입을 진행하며 지원자분에게 드렸던 인터뷰 질문은 interview.md에 있습니다. 문제를 풀어보시고 이 문서도 확인해보세요.
사건은 1885년 한 조그마난 팜플렛이 버지니아에서 발견되면서부터 시작된다. 이 팜플렛에는 빌이라는 이름의 한 남자의 이야기와 세 개의 암호 메세지가 담겨있었다.
이야기의 내용은 1820년 빌이라는 남자가 버지니아 베드포드 카운티 한 비밀의 장소에 보물로 가득 찬 수레 두 대를 묻었다는 것이다.
이 남자는 여관 주인에게 작은 열쇠 상자를 맡기고 마을을 떠난 뒤 다시는 나타나지 않았다. 수 년 뒤 여관 주인은 열쇠 상자를 열었고 세 개의 암호화된 메세지를 발견한다.
그는 평생 암호를 해독하지 못하고 1863년 죽기 전에 친구에게 암호를 준다. 그로부터 20년 후 이 이름 모를 친구는 세 개의 암호 중 첫 번째와 두 번째 암호를 해독하는데 성공한다.
해독된 메세지에는 빌이 묻은 금은보화들의 존재와 위치가 담겨있었다. 마지막 메세지에는 세부 위치와 그 보물들이 누구의 소유인지 밝혀져 있다고 한다.
수십 년간 많은 사람이 암호 해독을 시도해보았고 보물을 찾아 나섰지만 모두 실패했다.
빌의 두번째 암호
빌의 세번째 암호
그러던 중 카카오 추천팀 레오는 빌의 다른 암호문 중에서 세 번째 암호를 해결하기 위한 단서가 첫 번째 암호와 두 번째 암호에 존재한다는 사실을 발견했다.
첫 번째 암호문을 행렬로 표현했을 때 k x k 크기의 정방 블록부분행렬들 중 한 블록부분행렬 X와 X와 같은 크기의 두 번째 암호의 블록부분행렬들 중 한 블록부분행렬 Y가 세 번째 암호를 해독하는데 중요한 역할을 한다는 사실을 발견한 것이다.
레오는 세 번째 암호문의 k x k 크기의 블록부분행렬 집합 Q의 원소 중 의미있는 원소의 집합 S를 다음과 같이 표현하였다.
레오는 집합 S의 크기가 클수록 암호를 해독할 가능성이 높아진다고 생각하였지만 모든 경우를 전부 해보는 것은 시간상 힘들기 때문에 X, Y 그리고 세 번째 암호문 n×m 행렬 R이 주어졌을 때 |S|를 구하는 프로그램을 구현하고자 한다.
- 입력제한
- C++, Java : 1 ≤ k ≤ 100, k ≤ n, m ≤ 150
- Python : 1 ≤ k ≤ 40, k ≤ n, m ≤ 60
- k×k의 두 행렬의 곱 연산은 일반적인 방법으로 O(k^3)에 구현이 가능하고 가장 빠른 방법은 O(k^2.373)에 구하는 방법으로 알려져 있다.
하지만 위 두 가지 방법론으로 위 문제를 해결하기에는 적절하지 않기 때문에 다음 방법론을 이용하여 구현해야 한다. - Standard Library만 사용해야 한다. (ex Python 2, Python 3 - numpy 모듈 허용하지 않음)
- 제한시간 C++ 1.5초, Java 2.5초, Python 5초
- 표준 입출력 사용
- matrix 연산 과정은 int 범위 안에서 계산할 수 있습니다.
첫 번째 줄에 테스트 케이스 T(1 ≤ T ≤ 10)가 입력으로 주어진다. 두 번째 줄부터 테스트케이스가 시작된다.
각 테스트 케이스의 첫 번째 줄에 공백을 기준으로 n, m, k가 주어진다. 그 다음줄부터 k개의 줄에는 X의 원소가 k개씩 주어진다.
이어서 k개의 줄에는 Y의 원소가 k개씩 주어지고 그 다음에 n개의 줄에 R의 원소가 m개씩 주어진다.
각 테스트케이스마다 |S| 를 한 줄에 하나씩 출력한다.
| 입력 예제 | 출력 예제 |
|---|---|
| 2 1 4 1 2 6 3 4 3 3 3 4 2 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 3 1 -1 |
3 2 |