[백준 11727] 2×n 타일링 2 [C]

백준 - 11727

---

풀이

"백준 11726, 2×n 타일링" 문제와 비슷하다. 심지어 정답도..

2x1 타일을 1, 1x2 타일을 2, 2x2 타일을 T라고 가정할 때 다음과 같이 나타낼 수 있다.

N	타일	dp[1]
2	11 2, T	3
3	111 12,1T 21,2T	5
4	1111 112,11T 121,1T1 211,T11 22,TT 2T,T2	11
5	11111 1112,111T 1121,11T1 1211,1T11 2111,T111 122,1TT 212,T1T 221,TT1 12T,1T2 21T,T12 2T1,T21	21
6	"	43
7	"	85
8	"	171

N번째 방법의 수는 "2 * (N-2번째 방법의 수) + (N-1번째 방법의 수)" 와 같음을 알 수 있다.

---

소스코드

#include <stdio.h>
#define MOD 10007
int main(){
    int N, dp[2] = {0, 1};
    scanf("%d", &N);
    while (N--){
        int temp = (2*dp[0]+dp[1])%MOD;
        dp[0] = dp[1], dp[1] = temp;
    }
    printf("%d", dp[1]);
}

---

출처

11727번: 2×n 타일링 2