https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
2 * i 크기의 직사각형을 주어진 타일들로 채우는 방법의 수를 k[i]라고 하자.
이때 우리가 사용할 수 있는 가장 작은 블록의 단위는 2 * 1 블록인 "l"과, 2 * 2 블록인 "="일 것이다.
2 * 2 블록 중 "ll"블록은 2 * 1블록 두 개로 만들 수 있기에 이 블록은 가장 작은 단위의 블록이 아니다.
또한, 1 * 2블록인 "-" 역시 이 블록 하나만으로는 2 * i 크기의 직사각형을 완전히 채울 수 없기 때문에 가장 작은 단위의 블록이 아니다.
2 * i 크기의 직사각형을 어떻게 채워 넣어야 하는지에는 두 가지 방법이 있다.
- 2 * (i - 1)크기의 직사각형의 맨 앞에 2 * 1 크기의 직사각형("l")을 하나 추가하는 방법
- 2 * (i - 2)크기의 직사각형의 맨 앞에 2 * 2 크기의 직사각형("=")을 하나 추가하는 방법
2 * (i - 3)크기의 직사각형의 맨 앞에 2 * 3 크기의 직사각형을 추가할 수 있지 않느냐고 물을 수 있다.
그러나 2 * (i - 3)크기의 직사각형의 맨 앞에 2 * 3크기의 직사각형을 추가하는 경우의 수는 2 * (i - 1)크기의 직사각형의 맨 앞에 2 * 1 크기의 직사각형을 하나 추가하는 방법, 그리고 2 * (i - 2) 크기의 직사각형의 맨 앞에 2 * 2 크기의 직사각형을 하나 추가하는 방법들과 중복된다.
즉, 우리는 추가할 수 있는 최소단위의 블록인 "l"과 "="만을 기존의 직사각형에 추가해야 중복되는 경우의 수가 발생하지 않는다.
위 사실들을 바탕으로 다음과 같은 k[i]를 구하는 식을 얻을 수 있다.
k[i] = k[i - 1] + k[i - 2]
k[i - 1]크기의 직사각형에서 최소단위 블록 중 하나인 "l" 블록을 추가하는 경우의 수와 k[i - 2]크기의 직사각형에서 최소단위 블록 중 하나인 "=" 블록을 추가하는 경우의 수를 합한 값이 k[i]가된다.
이때, k[1] = 1 ( "l"), k[2] = 2 ("ll", "=")이다.
https://www.acmicpc.net/problem/11727
11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
11727번 문제의 경우 우리가 사용할 수 있는 블록이 추가된다.
기존의 "l", "="에 더해 "□" 역시 사용할 수 있다.
이 경우에도 2 * i 크기의 직사각형을 채워넣는 방법은 기본적으로 같다.
- 2 * (i - 1)크기의 직사각형의 맨 앞에 2 * 1 크기의 직사각형("l")을 하나 추가하는 방법
- 2 * (i - 2)크기의 직사각형의 맨 앞에 2 * 2 크기의 직사각형("=")을 하나 추가하는 방법
그러나 우리가 사용할 수 있는 최소단위의 블록이 하나 더 추가되었기 때문에 위 방법에서 하나의 방법이 더 추가된다.
- 2 * (i - 2)크기의 직사각형의 맨 앞에 2 * 2 크기의 직사각형("□")을 하나 추가하는 방법
이렇게 새로 추가된 최소단위 블록을 고려한 k[i]의 값은 다음과 같다.
k[i] = k[i - 1] + 2 * k[i - 2]
2 * (i - 2) 크기의 직사각형의 앞에 추가할 수 있는 최소단위 블럭이 2개가 되었으니 기존의 k[i - 2]에 2를 곱해준 값을 더하는 것을 확인할 수 있다.
정리하자면 다음과 같다.
- 우리가 사용 가능한 최소단위 블록을 파악한다.
- 2 * i 크기의 직사각형을 만들기 위해 그 보다 작은 직사각형에서 최소단위 블록을 더해 2 * i 크기의 직사각형을 만들 수 있는 경우의 수를 파악한다.