dp[i] = 1 * dp[i - 1] + 2 * dp[i - 2] + 3 * dp[i - 3] ... dp[i - K] 위와 같은 점화식으로 dp[N]를 구해야 한다고 생각해보자. 일단 dp를 하나하나 구한다고 하면 총 O(NK)의 시간복잡도가 나올 것이다. 그러나 이를 잘 최적화하면 O(K^3 log N) 안에 dp[N]을 구할 수 있다. 바로 행렬 거듭제곱을 이용하는 것인데, 그 전에 "행렬 곱셈을 한다"가 어떤 의미인지 한 번 해석을 해보도록 하겠다. 다음과 같은 행렬 두 개가 있다고 가정하자. [1, 2, 3] [10] [1, 0, 0] [20] [0, 1, 0] [30] 그리고 위 행렬을 곱하면, 다음과 같은 행렬이 나올 것이다. [1*10+2*20+3*30 = 140] [1*10+0*20+0..
