[12797] 연금술

https://www.acmicpc.net/problem/12797

12797번: 연금술

고생 고생 끝에 겨우 풀었다. 정리해둘만한 내용이 많은 문제인 것 같아서 풀이를 기록해 둠.

 

우선 점화식부터 유도해보자. $ DP(n, m) $ 을 $1 \dots m $ 번 까지의 재료를 써서 $ n $ 개 조합할 때 만들 수 있는 완성품 품질의 총합이라고 정의한다. 이 경우 $ DP(n, m) $의 점화식은 다음과 같이 세울 수 있다.

 

$$ DP(n, m) = a_m \cdot DP(n - 1, m) + DP(n, m - 1) $$

 

 $m$ 번 재료를 한 번 더 포함 시킬지 / 더이상 $m$ 번 재료를 포함시키지 않고 $m-1$번 재료를 포함시키는 단계로 넘어갈 건지 고르는 것이므로 비교적 직관적으로 점화식을 유도할 수 있다.

 

 이제 이 점화식을 조금 더 풀어 써보면, $DP(n, m - 1) = a_{m-1} \cdot DP(n - 1, m - 1) + DP(n, m - 2)$ 이고, 다시 $DP(n, m - 2) = a_{m-2} \cdot DP(n - 1, m - 2) + DP(n, m - 3)$ 이고, ... 이 형태가 반복되므로 식을 아래와 같이 정리할 수 있다.

 

$$ DP(n, m) = \sum_{k=1}^{n}{a_k \cdot DP(n - 1, k)} $$

 

이런 점화식은 각 행에 대해 계수를 행렬로 분리하고 보면 행렬 곱 형태로 나타낼 수 있다. 맨 첫번째 행이 $a_1, 0, \dots, 0, 0$ , 그 다음 행이 $a_1, a_2, \dots, 0, 0 $, 다시 그 다음 행이 $a_1, a_2, a_3, \dots, 0, 0 $, ... 형태로 이루어진 행렬을 생각해보자. 즉, $i$번째 행은 맨 처음 $i $ 열에는 $a_i$가 적혀 있고, 그 다음 열들에 대해서는 $0$이 적혀 있다. 그러니까 삼각 행렬의 형태를 가진다. 이 행렬을 A라고 하고 다음 식을 생각해보자.

 

$$ A \left\lbrack \matrix{DP(n-1,1) \cr DP(n-1,2) \cr \vdots \cr DP(n-1,m)} \right\rbrack $$

 

행렬 A에 $DP(n-1, 1)$ 부터 $DP(n-1, m)$ 까지 값을 순서대로 나열한 열벡터를 곱한 것이다. 이 때 행렬 곱셈식을 위에 적은 점화식을 바탕으로 정리하면 이 곱셈의 결과는

 

$$ \left\lbrack \matrix{DP(n,1) \cr DP(n,2) \cr \vdots \cr DP(n,m)} \right\rbrack $$

 

이 된다. 즉, 곱셈을 하고 나면 벡터의 모든 $i$번째 위치 값에 대해 $DP(n-1, i)$ 가 $DP(n, i)$로 바뀐다.

 

이렇게 행렬 곱 형태로 나타내면, 행렬 곱을 $n$번 하는 건 행렬의 빠른 거듭 제곱을 이용해 $O(logN)$ 번의 행렬 곱만으로 계산할 수 있다. 행렬 곱은 한 번에 $O(M^3)$의 시간이 걸리므로, 총 시간 복잡도 $O(M^3logN)$에 문제를 해결할 수 있다. 원래의 $O(NM)$ 시간 복잡도에 비해 빠르긴 하나 이 방법으로도 해당 문제를 풀기에는 충분히 빠르지 못하다.

 

 여기서 속도를 최적화하기 위해 행렬의 대각화를 이용한다. 행렬의 대각화는 어떤 행렬 $A$가 있을 때, $D=Q^{-1}AQ$ 이면서 $D$가 대각행렬(주 대각선 외에는 전부 값이 0인 행렬)임을 만족하는 $D$를 구하는 것을 말한다. 행렬을 대각화할 경우 우리가 구하고자 하는 식은 $Q D^n Q^{-1} B$ 가 된다. 여기서 $D^n$ 은 $D$가 대각행렬이므로 $O(MlogN)$ 시간에 구할 수 있다.

 

 비슷하게, $D$가 대각행렬이므로 $Q D^n$ 을 구하는 과정은 $O(M^2)$ 시간에 계산할 수 있다. $B$가 벡터이므로 $Q^{-1} B$ 역시 $ O(M^2) $ 시간에 구할 수 있고, 이 둘을 다시 곱하는데에도 $O(M^2)$의 시간이면 충분하므로 전체 시간복잡도 $O(M^2)$에 문제를 해결할 수 있다.

 

 이제 남은 과정은 행렬을 대각화할 수 있는지 여부 및 대각화하는 방법을 찾는 것이다. 이 때, 우리가 만든 행렬은 삼각 행렬이며 주 대각선의 모든 수가 서로 다르다(문제에서 $a_i$는 전부 서로 다른 수라고 명시했기 때문). 주 대각선의 모든 수가 서로 다른 삼각 행렬은 항상 대각화가 가능하다. 삼각행렬이기 때문에 주 대각선에 위치한 수가 전부 해당 행렬의 고유값이 되고, 이 수들이 전부 서로 다르므로 $m$개의 고유값이 존재한다. 고유값이 주 대각선에 위치한 수와 일치하므로, 대각 행렬 $D$의 주 대각선에는 $a_1, a_2, \dots, a_m$이 존재하게 된다. 이제, 행렬 $Q$와 $Q^{-1}$만 구하면 문제를 해결할 수 있다.

 

 이 때 주어진 행렬의 모든 고유벡터를 구하는 건(그러니까 행렬 $Q$를 구하는 건) 비교적 간단하게 $O(M^2)$에 수행할 수 있다.  행렬 $Q$의 주 대각선을 모두 1로 채우고, 고유벡터를 구하기 위해 행렬 $A$ 에서 각각의 고유값 $a_i$를 뺀 경우에 대해 조건을 만족하게끔 $Q$의 값을 채운다고 생각해보자. 쭉 나열해놓고 보면, 바로 $Q$의 값을 채워넣을 수 있는 칸이 항상 존재한다. 이 칸들을 채우는 식이 어떻게 되는지 정리해보면 규칙성이 존재해서 $Q$ 행렬을 $O(M^2)$ 시간에 구할 수 있다. 어떤 규칙성이 있는지는 식을 적기가 너무 번거로워서 생략. 직접 유도해보면 어렵지 않게 찾을 수 있다.

 

 이제 행렬 $Q^{-1}$을 구하는게 문제인데, 이 역행렬을 그냥 계산하려고 하면 식이 깔끔하게 떨어지지 않는다. 여기서는 $Q^{-1}$이 궁금한게 아니라 $Q^{-1}B$ 가 궁금하다는 것에 착안하자. $Q^{-1}B = X$라고 하면, $B =QX$를 만족한다. $Q$ 행렬은 계산 가능하며 삼각 행렬이다. 따라서 삼각 행렬의 맨 아래칸(1칸 밖에 없는 위치)부터 시작해서 순서대로 $X$의 각 변수를 확정지어나가면 $O(M^2)$ 시간에 $Q^{-1}B$도 계산 가능하다. 따라서 전체 시간 복잡도 $O(M^2)$에 문제를 풀 수 있다.

 

 선형대수를 원래 잘 못하기도 하고 관련 문제를 풀어본 적이 거의 없다시피해서 정말 한참을 고생해서 풀었다. 덕분에 선형대수와 관련해서 많이 배운 것 같다..