[12797] 연금술
마지막 수정 시각: 2020-10-26 22:03:12
고생 고생 끝에 겨우 풀었다. 정리해둘만한 내용이 많은 문제인 것 같아서 풀이를 기록해 둠.
우선 점화식부터 유도해보자. \( 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\)를 다음과 같이 정의할 수 있다.
\[ A = \begin{bmatrix} a_1 & 0 & 0 & \cdots & 0 & 0 \\ a_1 & a_2 & 0 & \cdots & 0 & 0 \\ a_1 & a_2 & a_3 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ a_1 & a_2 & a_3 & \cdots & a_{m-1} & 0 \\ a_1 & a_2 & a_3 & \cdots & a_{m-1} &a_m \end{bmatrix} \]
이 행렬 \(A\)에 \(DP(n-1, 1)\) 부터 \(DP(n-1, m)\) 까지 값을 순서대로 나열한 열벡터를 곱한다고 생각해보자. 즉, 아래와 같은 식을 생각해보자.
\[ A \begin{bmatrix} DP(n-1,1) \\ DP(n-1,2) \\ \vdots \\ DP(n-1,m) \end{bmatrix} = B \]
이 때 행렬 곱셈식을 위에 적은 점화식을 바탕으로 정리하면 이 곱셈의 결과 \(B\)는
\[ B = \begin{bmatrix} DP(n,1) \\ DP(n,2) \\ \vdots \\ DP(n,m) \end{bmatrix} \]
이 된다. 즉, 곱셈을 하고 나면 벡터의 모든 \(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)\)에 문제를 풀 수 있다.
선형대수를 원래 잘 못하기도 하고 관련 문제를 풀어본 적이 거의 없다시피해서 정말 한참을 고생해서 풀었다. 덕분에 선형대수와 관련해서 많이 배운 것 같다..