목록점화식 (2)
Joonas' Note
링크: https://www.acmicpc.net/problem/2133 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 풀이 3×N 벽을 채우는 경우를 \(f(n)\), 한 칸이 빈 3×N 벽을 채우는 경우를 \(g(n)\) 라고 하자. 왼쪽부터 2×1 또는 1×2 크기의 타일을 하나씩 채워보면서 가능한 경우를 살펴본다. \(g(0)\)와 \(g(2)\)는 타일을 채울 방법이 없으므로 \(g(0) = g(2) = 0\) 이다. 이것을 식으로 나타내면 이렇다. $$f(n) = \begin{cases} 0 & \text{if $n$ < 2} \\ 2g(n-1) + f(n-2) \end{cases}$$ $$g(n) = \begin{cases} 1 & \text{i..
링크 1: https://uva.onlinejudge.org/...problem=1859 링크 2: BOJ 2133 - 타일채우기(https://www.acmicpc.net/problem/2133) 문제 타일 시리즈 중에 하나로, 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 문제이다. 풀이 3×n 크기의 벽을 채우는 경우의 수를 \(f(n)\)이라고 하자. 다음은 전개될 수 있는 모든 모양이다. 모양이 반복되는 경우까지만 적었다. .... x... .... f(n) = .... g(n) = .... or .... .... .... x... A..... AA.... A..... or ...... ...... ...... A..... ACC... ACC... ACC... A..... -> A....