C언어 백준 11726번 2×n 타일링

문제

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

문제풀이

#include <stdio.h>

int arr[1001];
int num;
void solution(int n);

int main(void)
{
	scanf("%d",&num);
	solution(num);
}


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

타일의 개수를 처음부터 나열하면 피보나치 수열을 의미함을 알 수 있다. 배열을 통해 직사각형 크기별 개수를 배열 인덱스에 맞게 적는다. 예를 들어 arr[1]인 경우 2x1의 크기일 때 개수, arr[2]인 경우 2x2의 크기일 때 개수 등의 값이 들어간다.

 

결과적으로 arr[i]=arr[i-1]+arr[i-2] 식이 완성된다.