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

문제 풀이

점화식을 세우고 메모이제이션을 통해 n번째 값을 구하는 형태입니다.

노트에 2xn의 타일링을 만들고 경우의 수를 세어가면서 하나씩 값을 나열하였습니다. 

첫 번째 2x1 타일링 개수 : 1

두 번째 2x2 타일링 개수 : 3

세 번째 2x3 타일링 개수 : 5

여기까지 나열하였을 때, 피보나치 또는 단순 덧셈이 아닌 것을 확인하였습니다.

네 번째 2x4 타일링 개수 : 11

 

더 이상 나열하는 것은 너무 많은 개수를 요구하는 것 같아 네 번째까지 두고 추론하였습니다. 실제 시험이라면 시간을 보고 다섯 번째까지 해 보았을 것입니다.

 

결과적으로 a[n]=a[n-1]+2*a[n-2]라는 식을 세울 수 있었습니다.

코드

 

#include <stdio.h>

int n;
int arr[1010]={0,};
	

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