[백준][11726번][DP] 2xn 타일링

2xn 타일링

https://www.acmicpc.net/problem/11726

<코드>

#include <stdio.h>
 
int main(void){
 
    int Dp[1010] = {};
    int n;
    Dp[0] = 1; Dp[1] = 1;
 
    scanf("%d", &n);
 
    for (int i = 2; i <= n; i++)
        Dp[i] =  (Dp[i - 1] +Dp[i-2])%10007;
 
    printf("%d\n", Dp[n] % 10007);
    return 0;
}

<문제 푼 요령>

1. Dp[i] 의 값을 만드는 경우는 앞에 타일이 1개 세로로 있을 경우와 앞에 타일이 2개 가로로 있을 경우를 더하면 된다.

2. 즉 Dp[i] = Dp[i-1] + Dp[i-2] 의 값을 저장해서 구하면 된다. 어찌보면 피보나찌 수열과 같다.