2xn 타일링 _ 백준 11726, 백준 11727

11726번 문제와 11727문제는 하나의 조건만 달라서 한번에 정리해보려고 한다.

 

11726

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

2×n 타일의 우측에 칸을 채워넣는 방식으로 생각하면, 방법은 두가지이다.

1.  1×2가 들어가게 되면 한칸이 완전히 차게 되고,  2 X n-1이 남는다.  → d[n-1]
2. 2 X 1 이 들어가게 되면 두칸이 차게되고, 2 X n-2가 남는다 → d[n-2]

DP문제이니만큼, 점화식을 세워보면,

2 x n 크기의 타일을 채우는 방법의 수를 d[n]이라고 하면 d[n] = d[n-1] + d[n-2]이 되는 것이다.

 

여기서 조금 헤맨 부분을 이야기하자면, 그냥 이렇게 세워서 문제를 풀다보니 계속 답이 틀렸다고 하는 문제가 있었다.

알아보니까 계속 숫자를 더하다보면 자료형의 크기를 넘을 수 있기 때문에 그냥 10007로 나눈 나머지를 저장해야 런타임 에러를 방지할 수 있다고 한다.

#include <cstdio>
using namespace std;
int d[1001];

int main(void)
{
    d[0] = 1;
    d[1] = 1;
    int n;
    scanf("%d", &n);
    for (int i = 2; i <= n; i++)
    {
        d[i] = d[i - 1] + d[i - 2];
        d[i] %= 10007;
    }
    printf("%d", d[n]);
    return 0;
}

 

 

11727

2×n 직사각형을 1×2, 2×1과 2×2(추가된 부분) 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

대부분의 내용은 11726과 같다. 

 

2×n 타일의 우측에 칸을 채워넣는 방식으로 생각하면, 방법은 세가지이다.

1.  1×2가 들어가게 되면 한칸이 완전히 차게 되고,  2 X n-1이 남는다.  → d[n-1]
2. 2 X 1 이 들어가게 되면 두칸이 차게되고, 2 X n-2가 남는다 → d[n-2]
3. 2 X 2 가 들어가게 되면 역시 2와 같이 두칸이 차고, 2 X n-2가 남는다 → d[n-2]

즉 2 x n 크기의 타일을 채우는 방법의 수를 d[n]이라고 하면 d[n] = d[n-1] + 2 * d[n-2]이 되는 것이다.

 

나머지는 11726과 같다.

 

#include <cstdio>
using namespace std;
int d[1001];

int main(void)
{
    d[0] = 1;
    d[1] = 1;
    int n;
    scanf("%d", &n);
    for (int i = 2; i <= n; i++)
    {
        d[i] = d[i - 1] + 2 * d[i - 2];
        d[i] %= 10007;
    }
    printf("%d", d[n]);
    return 0;
}