CLASS 3 ESSENTIAL
\(2×n\) 크기의 직사각형을 1×2 직사각형과 2×1 직사각형으로 채우는 경우의 수를 구하는 문제입니다. 이 문제는 점화식을 이용하여(다른 말로 하면 다이나믹 프로그래밍으로) 풀 수 있는 문제입니다. 우선 \(n=1\)일 때와 \(n=2\)인 경우는 자명하게 각각 1가지와 2가지가 존재합니다. \(n\le 3\)일 때부터는 이전에 구한 값을 이용하여 구할 수 있습니다. 그 관계를 생각해보면 다음과 같습니다.
\(2×k\) 크기의 직사각형을 채우는 방법은 ① \(2×(k-1)\) 직사각형을 채운 경우에 2×1 직사각형을 덧붙이는 경우와 ② \(2×(k-2)\) 직사각형을 채운 경우에 1×2 직사각형 2개를 덧붙이는 경우의 합으로 볼 수 있다.
②의 경우에서 2×1 직사각형 2개를 붙이는 경우를 제외한 이유는 \(2×(k-2)\) 직사각형에 2×1 직사각형 하나를 붙여서 \(2×(k-1)\) 직사각형을 만들고 여기에 2×1 직사각형 하나를 더 붙이는 경우이므로 ①의 경우에 포함되기 때문입니다. 이를 이용하여 식을 써보면 아래와 같습니다.
\[a_n=a_{n-1}+a_{n-2},a_1=1,a_2=2\]이렇게 쓰고보니 피보나치 수열하고 많이 닮았습니다. 실제로 계산해보면 \(a_n=F_{n+1}\)이 나옵니다. 즉, 피보나치 수열을 구할 줄만 안다면 충분히 풀 수 있는 문제입니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-12-19 18:59:31 |