태그:
\(2×n\) 크기의 직사각형을 1×2 직사각형과 2×1 직사각형, 그리고 2×2 정사각형으로 채우는 경우의 수를 구하는 문제입니다. 이 문제는 11726 - 2×n 타일링 문제처럼 점화식을 이용하여 풀 수 있는 문제입니다. 위 문제처럼 풀면, \(n=1\)일 때와 \(n=2\)인 경우는 자명하게 각각 1가지와 3가지가 존재하고, \(n\le 3\)일 때는 관계가 다음과 같습니다.
\(2×k\) 크기의 직사각형을 채우는 방법은 ① \(2×(k-1)\) 직사각형을 채운 경우에 2×1 직사각형을 덧붙이는 경우와 ② \(2×(k-2)\) 직사각형을 채운 경우에 1×2 직사각형 2개를 덧붙이는 경우, ③ \(2×(k-2)\) 직사각형을 채운 경우에 2×2 정사각형을 덧붙이는 경우의 합으로 볼 수 있다.
②의 경우에서 2×1 직사각형 2개를 붙이는 경우를 제외한 이유는 \(2×(k-2)\) 직사각형에 2×1 직사각형 하나를 붙여서 \(2×(k-1)\) 직사각형을 만들고 여기에 2×1 직사각형 하나를 더 붙이는 경우이므로 ①의 경우에 포함되기 때문입니다. 이를 이용하여 식을 써보면 아래와 같습니다.
\[a_n=a_{n-1}+2\times a_{n-2},a_1=1,a_2=3\]굳이 풀자면 일반항은 \(a_n=\frac{(-1)^n}{3}+\frac{2\times 2^n}{3}\)이 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-12-19 20:20:57 |