관리 메뉴

Joonas' Note

BOJ 13976 - 타일 채우기 2 본문

알고리즘/문제 풀이

BOJ 13976 - 타일 채우기 2

joonas 2021. 9. 7. 19:36

링크: https://www.acmicpc.net/problem/13976

문제

2133번 문제와 같이 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제이지만, N의 범위가 \(10^{18}\) 이다.

풀이

이전에 작성한 2133번 문제의 2번째 풀이 방법과 같지만 그것을 빠르게 계산해야한다.

피보나치 수를 빠르게 구하는 방법과 마찬가지로, 행렬을 이용한 거듭 제곱 트릭을 사용하면 된다.

 

수열의 값은 같으므로, 편의상 OEIS A001835 수열 \( f(n) = 4 \cdot f(n-1) - f(n-2) \) 을 사용하겠다.

이것을 행렬로 나타내면 아래와 같다.

$$\begin{eqnarray} \left( \begin{array}{ccc} f_{n} \\ f_{n-1} \end{array} \right) & = & \left( \begin{array}{ccc} 4 \cdot f_{n-1} - f_{n-2} \\ f_{n-1} \end{array} \right) \\ & = & \begin{pmatrix} 4 & -1 \\ 1 & 0 \end{pmatrix}  \left( \begin{array}{ccc} f_{n-1} \\ f_{n-2} \end{array} \right) \end{eqnarray} $$

 

이렇게 중간에 4x4 행렬 ((4, -1), (1, 0)) 을 얻었고, 초기 항에 이것을 \(n\)번 제곱하면 \(f(n)\)을 구할 수 있다.

$$\left( \begin{array}{ccc} f_{n} \\ f_{n-1} \end{array} \right) = {\begin{pmatrix} 4 & -1 \\ 1 & 0 \end{pmatrix}}^{n} \left( \begin{array}{ccc} f_{2} \\ f_{1} \end{array} \right) = {\begin{pmatrix} 4 & -1 \\ 1 & 0 \end{pmatrix}}^{n} \left( \begin{array}{ccc} 3 \\ 1 \end{array} \right)$$

 

거듭 제곱을 빠르게 하는 트릭은 \(a^{4} = a^{2} \cdot a^{2}\) 을 이용해서, 한번 계산한 \(a^{2}\)를 재사용하는 방법이다. 이것을 행렬에도 그대로 적용할 수 있다.

 

코드

주의할 점은, 행렬 중간에 음수가 있을 수 있으니 모듈러를 통해 양수로 적절히 변환해줘야한다.

 

반응형

'알고리즘 > 문제 풀이' 카테고리의 다른 글

BOJ 13976 - 타일 채우기 2  (0) 2021.09.07
BOJ 2133 - 타일 채우기  (0) 2021.09.07
UVa 136 - Ugly Numbers  (2) 2020.07.06
BOJ 11012 - Egg  (1) 2020.06.10
[코딩으로 풀어보기] 95화 4번, 1~9까지 숫자로 식을 성립시켜라.  (0) 2020.06.10
BOJ 3640 - 제독  (0) 2020.05.24
0 Comments
댓글쓰기 폼