[백준 11726번] 2×n 타일링

1.  점화식

 

dp 배열을 순서대로 점화식을 생각해본다.

 

n = 1

2x1 타일을 세운다. |

dp[1] = 1

 

n = 2

1x2 타일 2개를 눕힌다 =

dp[2] = 2

 

n = 3

|||

|=

=|

dp[3] = 3

 

n = 4

||||

||=

|=|

=||

==

dp[4] = 5

 

n이 4일때

|로 시작하는 경우 + =으로 시작하는 경우로 나눌 수 있다.

|로 시작하는 경우(||||, ||=, |=|)에서 |를 빼면 |||, |=, =| 즉, dp[3]이되고

=로 시작하는 경우(=||, ==)에서 =를 빼면 ||,= 즉, dp[2]가 된다.

dp[4] = dp[2] + dp[3] 이 된다. ( 피보나치 )

 

2. 코드

#include <stdio.h>

int main()
{
    int n = 0;
    scanf("%d", &n);

    int dp[1001] = { 0,1,2 };
    
    for (int i = 3; i <= n; i++)
        dp[i] =  (dp[i - 2] + dp[i - 1])%10007;
    
    printf("%d", dp[n]);
    return 0;
}

 

포인트

#1 점화식 세우기

#2 시작하는 case 생각하기

#3 출력조건의 divisor 빠트리지 않기

#4 타일(|, =) 나열시 숫자로 생각하기