백준 11726번: 2xn 타일링

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

 

 

 

문제

 

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

 

 

 

 

n=1일 때

 

 

n=2일 때

 

 

n=3일 때

 

 

n=4일 때

 

 

 

 

 

그림을 살펴보자. n=3일때는 다음과 같이 나타낼 수 있다.

 

 

 

이것을 일반화하면 다음과 같다. 

 

 

 

즉, 2xn 크기의 직사각형을 채우기 위해서는 2x(n-1) 크기의 직사각형을 채우는 방법과 2x(n-2) 크기의 직사각형을 채우는 방법을 더하면 된다.

 

 

 

 

 

코드

 

#include <stdio.h>

int dp[1000001];

int main(){
	int n;
	scanf("%d",&n);

	dp[0] = 1;
	dp[1] = 1;

	for(int i = 2;i <= n;i++){
        // 2*(n-1) 타일의 뒤에 2*1 한 개 붙이는 경우
        // +
        // 2*(n-2) 타일의 뒤에 1*2 두 개 붙이는 경우
		dp[i] = (dp[i - 1] + dp[i-2]) % 10007;
	}

	printf("%d\n", dp[n]);
}