[백준] 11726번. 2xn 타일링 (C언어)

문제 설명

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하자

2×5 크기의 직사각형을 채운 방법의 예

1 <= n <= 1,000

n을 입력받은 후 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

 

 

문제 해결 방향

DP문제이다

이런식으로 계속 경우의 수를 찾아 볼 경우 피보나치 수열이라는 것을 알 수 있다.

 

#include<stdio.h>
#define _CRT_SECURE_NO_WARNINGS

int main() {

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

	int arr[1001];
	for (int i = 0; i < 1001; i++) { arr[i] = 0; }

	arr[1] = 1;
	arr[2] = 2;

	for (int i = 3; i <= n; i++)
	{
		arr[i] = (arr[i - 1] + arr[i - 2]) % 10007;
	}


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