11726번 : 2 x n 타일링

간단한 dp로 풀 수 있다. 

2 x i 타일은 2 x (i-2) 타일에 가로타일 2개를 붙인것과 2 x (i-1)타일에 세로타일 1개를 붙인 것을 더한 것과 같다.

따라서 dp식은 dp[i]=dp[i-1]+dp[i-2]이다.

여기서 dp는 10007로 나눈 값을 저장해야하므로 더하는 식에 %10007을 추가해준다.

#include <stdio.h>

#define R 10007

int dp[1000],N;

int main() {

dp[0] = 1;

dp[1] = 1;

scanf("%d", &N);

for (int i = 2; i <= N; ++i) {

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

}

printf("%d", dp[N]%R);

}