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

문제

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

입력과 출력

첫째줄에 n이 주어지면(1<=n<=1,000) 2*n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력

풀이

f(2) = 2

f(3) = 3

f(4) = 2*f(2) + 2*f(3) 인지 f(2)+f(3) 인지 헷갈린다

f(n)일때 f(n-1)에다가 1*2 타일을 이어 붙이는거고 f(n-2)에다가 2*1 타일 2개를 붙이는건데... 

앞뒤의 경우로 나눠서 생각해야하는지 항상 맨 뒤에 또는 맨 앞에 붙인다 생각해야하는지 헷갈렸다..

매우 쉬운문제였다 ㅠㅠ

코드

dp[1]=1;

dp[2]=2;

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

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

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