oVeron

1.우리가 \(n-1\)칸까지 타일을 채웠다면, 1칸, 2칸, ... \(n-1\)칸까지 채운 타일의 개수에 대한 정보로 \(n\)칸에 채울 타일의 개수를 DP를 이용해 구할 수 있다. \(dp[i] =  3 * dp[i-1]  + (2 * dp[i-2] + 2 * dp[i-3] + ... + 2 * dp[1])\)\(dp[i+1] = 3 * dp[i]  + 2 * dp[i-1] + (2 * dp[i-2] + ... + 2 * dp[1])\) 괄호 친 부분은 동일하므로, 두 식을 연립하면 다음과 같다. \(dp[i+1] = 4 * dp[i] - dp[i-1]\) 이는 선형 점화식이므로 분할 정복을 이용한 행렬 제곱으로 빠르게 구할 수 있다.이때 행렬에 음수가 포함되어 있으므로, 음수 모듈러 연산에 유의한..

알고리즘/baekjoon 2024. 6. 18. 20:11