[백준 알고리즘] 11727번 2*n 타일링 2

문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력은 2*n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지

풀이

전에 풀었던 2*n 타일링(11726번) 문제랑 거의 똑같은거 같은데 오늘 너무 문제 풀기싫으니까 동기부여용으로...다시 푼다

f(n)= 2*n 직사각형을 채우는 방법의 수

f(1) = 1

f(2) = 3 

f(3) = f(2) + f(1)*2

f(4) = f(3) + f(2)*2

f(n) = f(n-1)+f(n-2)*2 ->f(n-2)에 대해서 나란히 누워붙이는 경우+2*2 타일쓰는경우라서 2가지

코드

dp[1]=1;

dp[2]=3;

for(i=3; i<=n; i++)

dp[i]=(dp[i-1]+dp[i-2]*2)%10007;

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