나의 행렬곱셈 답사기

$n$개의 행렬 $\mathbf{M}_1, \mathbf{M}_2, \cdots, \mathbf{M}_n$의 곱, 즉 $\mathbf{M}_1 \mathbf{M}_2 \cdots \mathbf{M}_n$을 계산하는 일은 사람에게나 컴퓨터에게나 번거롭다.

행렬과 그 곱셈이 익숙하지 않은 사람을 위해 먼저 정리해 보자. 행렬은 여러 수나 기호를 직사각형 모양으로 배열한 뒤 괄호로 묶은 것이다. 이 문제에서는 행렬에 정수만 배열한다고 가정한다. 예를 들어 아래와 같은 것이 행렬의 한 예이다.

$\begin{pmatrix} 2 & 0 & 1 & 6 \\ 0 & 5 & 2 & 8 \\ 1 & 4 & -1 & 7 \end{pmatrix}$

행렬에 배열된 수를 성분이라고 한다. 행렬의 가로줄은 행이라고 부르며 위에서부터 차례로 제1행, 제2행, 제3행, ... 으로 이름을 붙인다. 행렬의 세로줄은 열이라고 부르며 왼쪽에서부터 차례로 제1열, 제2열, 제3열, ... 으로 이름을 붙인다. 행이 $m$개, 열이 $n$개인 행렬을 $m \times n$ 행렬이라고 한다. 제$i$행 제$j$열에 있는 성분은 그 행렬의 $(i, j)$ 성분이라고 하며, 행렬 $\mathbf{A}$의 $(i, j)$ 성분은 $A_{ij}$로 적는다.

실수의 곱셈과 마찬가지로 행렬의 곱셈도 두 행렬을 가지고 한다. $\mathbf{A}$가 $m \times n$ 행렬이고 $\mathbf{B}$가 $n \times p$ 행렬일 때, 곱 $\mathbf{AB}$는 $(i, j)$ 성분이 다음과 같은 $m \times p$ 행렬로 정의된다.

$(\mathbf{AB})_{ij} = \sum_{k=1}^{n} A_{ik} B_{kj}$

$\mathbf{AB}$의 성분 하나를 계산하려면 정수 곱셈이 $n$회 필요하고 $\mathbf{AB}$는 $m \times p$ 행렬이므로, 모든 성분을 계산하려면 정수 곱셈이 모두 $(m \times p) \times n = m \times n \times p$회 필요하다.

행렬의 곱셈은 $\mathbf{A}$의 열의 수와 $\mathbf{B}$의 행의 수가 같을 때에만 정의된다. 예를 들어 $3 \times 2$ 행렬과 $4 \times 5$ 행렬은 곱할 수 없다.

행렬의 곱셈에서는 교환법칙이 성립하지 않지만 결합법칙은 성립한다. 즉 $m \times n$ 행렬 $\mathbf{A}$, $n \times p$ 행렬 $\mathbf{B}$, $p \times q$ 행렬 $\mathbf{C}$에 대해 일반적으로 다음이 알려져 있다.

• $\mathbf{AB} \neq \mathbf{BA}$
• $\mathbf{ABC} = (\mathbf{AB})\mathbf{C} = \mathbf{A}(\mathbf{BC})$

행렬 여러 개를 곱할 때 행렬이 나열된 순서는 바꿀 수 없지만, 곱하는 순서는 마음대로 정할 수 있다. 그러면 곱하는 순서를 바꾸면 정수 곱셈의 횟수가 실제로 달라질까? $\mathbf{A}$가 $2 \times 4$ 행렬, $\mathbf{B}$가 $4 \times 3$ 행렬, $\mathbf{C}$가 $3 \times 5$ 행렬이라고 하고 곱 $\mathbf{ABC}$를 계산해 보자.

• $(\mathbf{A}\mathbf{B})\mathbf{C}$로 계산하면
  • $2 \times 4$ 행렬 $\mathbf{A}$와 $4 \times 3$ 행렬 $\mathbf{B}$를 곱할 때 정수 곱셈이 $2 \times 4 \times 3 = 24$회 필요하고, 그 결과로 $2 \times 3$ 행렬이 만들어진다.
  • $2 \times 3$ 행렬 $\mathbf{A}\mathbf{B}$와 $3 \times 5$ 행렬 $\mathbf{C}$를 곱할 때 정수 곱셈이 $2 \times 3 \times 5 = 30$회 필요하고, 그 결과로 $2 \times 5$ 행렬이 만들어진다.
  • 따라서 정수 곱셈이 모두 $24 + 30 = 54$회 필요하다.
• $\mathbf{A}(\mathbf{B}\mathbf{C})$로 계산하면
  • $4 \times 3$ 행렬 $\mathbf{B}$와 $3 \times 5$ 행렬 $\mathbf{C}$를 곱할 때 정수 곱셈이 $4 \times 3 \times 5 = 60$회 필요하고, 그 결과로 $4 \times 5$ 행렬이 만들어진다.
  • $2 \times 4$ 행렬 $\mathbf{A}$와 $4 \times 5$ 행렬 $\mathbf{B}\mathbf{C}$를 곱할 때 정수 곱셈이 $2 \times 4 \times 5 = 40$회 필요하고, 그 결과로 $2 \times 5$ 행렬이 만들어진다.
  • 따라서 정수 곱셈이 모두 $60 + 40 = 100$회 필요하다.

행렬 3개를 곱할 때에도 곱하는 순서에 따라 정수 곱셈의 횟수가 달라지니, 행렬 $n$개를 곱할 때에도 마찬가지다. 행렬의 수가 많아지면 곱하는 방법도 많아진다. 예를 들어 $n = 4$일 때 행렬 $\mathbf{M}_1, \mathbf{M}_2, \mathbf{M}_3, \mathbf{M}_4$를 곱하는 방법에는 아래 5가지가 있다.

• $\big((\mathbf{M}_1\mathbf{M}_2)\mathbf{M}_3\big)\mathbf{M}_4$
• $\big(\mathbf{M}_1(\mathbf{M}_2\mathbf{M}_3)\big)\mathbf{M}_4$
• $(\mathbf{M}_1\mathbf{M}_2)(\mathbf{M}_3\mathbf{M}_4)$
• $\mathbf{M}_1\big((\mathbf{M}_2\mathbf{M}_3)\mathbf{M}_4\big)$
• $\mathbf{M}_1\big(\mathbf{M}_2(\mathbf{M}_3\mathbf{M}_4)\big)$

어떤 방법을 택해도 결과는 같으므로, 정수 곱셈이 가장 적게 필요한 방법을 택하면 행렬을 곱하는 데 걸리는 시간이 최소가 된다.

계산을 좋아하는 승현이는 최근 이렇게 행렬 $n$개를 곱하는 법을 배웠고, 예제를 몇 개 계산해 보더니 곱셈의 매력에 푹 빠졌다. 성분끼리 곱한 것을 모두 더하는 것이 참 아름답다고 한다.

승현이는 정수 곱셈을 0의 시간에 해내기 때문에 "행렬을 곱할 때 필요한 정수 곱셈 횟수를 굳이 최소화할 필요가 있을까?"라는 의문을 품고 선생님께 질문했다. 선생님은 최악의 정수 곱셈 횟수와 최적의 정수 곱셈 횟수의 차가 상당히 커지는 경우가 있어서, 정수 곱셈에 시간이 걸리는 보통 사람에게는 곱셈 횟수를 최소화하는 일이 중요하다고 답했다. 여기서 최악과 최적의 정수 곱셈 횟수는 행렬을 곱하는 모든 방법 가운데 정수 곱셈이 가장 많이 필요한 방법의 횟수와 가장 적게 필요한 방법의 횟수를 뜻한다.

보통 사람의 심정에 전혀 공감하지 못한 승현이는 질문을 이어갔고, 질문 공세에 지친 선생님은 결국 모든 자연수 $K$에 대해 최악의 정수 곱셈 횟수와 최적의 정수 곱셈 횟수의 차가 정확히 $K$인 행렬 $\mathbf{M}_1, \mathbf{M}_2, \cdots, \mathbf{M}_n$이 항상 존재한다고 답했다.

충격을 받은 승현이는 당신에게 그런 행렬을 하나 찾아 달라고 부탁해 왔다. $K$가 주어질 때 최악의 정수 곱셈 횟수와 최적의 정수 곱셈 횟수의 차가 정확히 $K$인 행렬들의 크기를 찾아내는 프로그램을 작성하자.

첫 줄에 정수 $K$ ($1 \le K \le 10^9$)가 주어진다.

첫 줄에 행렬의 개수 $N$ ($1 \le N \le 100$)을 출력한다. 둘째 줄에는 행렬의 크기를 나타내는 $N+1$개의 양의 정수 $a_0, a_1, \ldots, a_N$을 공백으로 구분해 출력한다. 행렬의 크기는 차례로 $a_0 \times a_1$, $a_1 \times a_2$, ..., $a_{N-1} \times a_N$이며, 이 $N$개의 행렬을 곱할 때 최악의 정수 곱셈 횟수와 최적의 정수 곱셈 횟수의 차가 정확히 $K$여야 한다.

조건을 만족하는 답이 여러 개면 사전순으로 가장 작은 답 하나만 출력한다. 즉 $N$이 가장 작은 답을 먼저 고르고, $N$이 같은 답이 여러 개면 수열 $(a_0, a_1, \ldots, a_N)$을 앞에서부터 비교해 가장 작은 것을 고른다.