알고리즘_타일 채우기 문제

문제)타일채우기(S)

2x1 혹은 2x2 크기의 타일을 2xn 크기의 직사각형 모양 틀에 넣으려고 한다. 이 때 가능한 경우의 수를 구하여라.

 경우의 수가 커지므로, 주어지는 수 m으로 나눈 나머지를 출력한다.

<입력>

첫 줄에는 직사각형 틀의 가로 길이 n이 주어진다.

둘째 줄에는 m이 주어진다 (1<=n<=100,000, 1<=m<=40,000)

<출력>

경우의 수를 m으로 나눈 나머지를 출력한다.

풀이)타일채우기(S)

문제를 관계기반으로 해결하기 위해서는 먼저 문제의 상태를 정의해야 한다. 

이러한 문제가 관계기반으로 풀리기 위해서는 타일을 채우는 순서에 관계가 없어야 한다. 

즉, 가운데에서부터 타일을 채우나 맨 끝에서부터 채우나 처음부터 채우나 같다.

따라서 처음부터 채워나간다 할 떄 f(n)은 아래와 같다.

위와 같이 정의하고, 수학적 귀납법에 의하면 반드시 직접적으로 해결해야 하는 작은 문제들이 있어야 한다.

일단 다음과 같이 작은 문제들에 대해 직접 해를 구한다.

(이런 경우의 수를 세는 문제는 아무것도 안 채우는 경우도 1가지로 카운팅 한다는 점을 알아두어야 한다.)

작은 케이스의 경우의 해는 다음과 같다.

f(0) = 1 “즉 아무것도 안 채우는 경우는 1가지”

f(1) = 1 “2x1의 판을 채우는 경우도 1가지”

f(2) = 3 “2x2의 판을 채우는 경우는 3가지

구하고자 하는 해 f(n)을 구하기 위해 f(1), f(2), ..., f(n-1)은 이미 구해두었다고 가정한다.

f(k)로부터 f(n)을 만드는데 마지막으로 사용할 수 있는 타일은 3가지가 있다.

1. 2x1을 이용하여 f(n)으로 만드는 경우

f(n-1)까지는 모두 채워져 있어야 2x1타일을 이용하여 f(n)을 만들 수 있다.

f(n-1)

n-1가지를 채운 경우로부터 2x1의 타일을 이용하여 f(n)을 만들 수 있는 경우는

그냥 뒤에 붙이는 1가지 뿐이다. 따라서 f(n)을 채우는 방법은 f(n-1)임을 알 수 있다.

f(n)

즉, f(n-1)을 모두 채우는 경우의 수를 알면 f(n)중 2x1을 이용하여 채우는 경우의 수를 알 수 있다.

2. 1x2를 이용하여 f(n)으로 만드는 경우

적어도 f(n-2)까지는 채워진 상태를 알 수 있어야 마지막으로 1x2를 이용하여 f(n)을 만들 수 있는 경우의 수를 알 수 있다.

f(n-2)

위 상태에서 f(n)을 구하기 위해 1x2타일을 배치해 보면 아래와 같다.

f(n)

위의 한가지 방법만 존재, 따라서 1x2타일을 이용하여 f(n)을 만들 수 있는 방법은 f(n-2)이다.

3. 2x2를 이용하여 f(n)으로 만드는 경우

1x2의 경우와 마찬가지로 f(n-2)까지의 상태를 알고 있어야 f(n)을 구할 수 있다.

f(n-2)

2x2타일을 배치하는 경우의 수는 아래의 경우 한가지 뿐이다. 따라서 f(n)을 만들 수 있는 방법은 f(n-2)가지이다.

f(n)

위의 관계로부터 얻어낸 점화식은 다음과 같다.

이미 구해둔 초깃값을 이용하여 정리하면,

첫번째 식을 다시 정리하면 아래와 같다.

code)타일채우기(S)

#include<iostream>
 
using namespace std;
 
int n, m;
 
int f(int k)
{
    if (k <= 1) return 1 % m;
    else return (f(k - 1) + 2 * f(k - 2)) % m;
}
 
int main()
{
    cin >> n >> m;
    cout << f(n) << endl;
 
    return 0;
}

이 방법은 쉽게 구현이 가능하나, 계산량이 너무 많아 n이 40정도의 값이더라도 너무 많은 시간이 걸린다.

계산량은 약 O〖(2〗^n) 이다.

효율적으로 처리하기 위해서는 새로운 관계식을 유도할 필요가 있다.