[백준]_11726번 : 2xn 타일링(파이썬 and C언어)

11726번: 2×n 타일링

이 문제가 어렵게 느껴진 이유는 우리가 타일을 쌓는 접근 방식을 절대로 컴퓨터한테 옮길 수 없기 때문이다. 우리는 타일을 하나하나 배열해서 모든 경우의 수를 찾지만 컴퓨터는 고작 타일 하나도 쌓지 못하는 상황이다. 따라서 타일 배열이 가능한 경우의 수를 나열해 봐서 어떤 규칙이라도 있는지 찾아보자

---

n에 따라 가능한 배열의 경우의 수를 T(n)이라고 정의하자. 따라서 n을 4까지 조사하면 아래와 같은 결과를 얻을 수 있다.

n	T(n)
1	1
2	2
3	3
4	5

피보나치 냄새가 나긴 한다만.. 확신을 하기 위해서는 더 명확한 증거가 있어야 한다! 그래서 아래와 같은 전략을 살펴보자. 예를 들어 n=k라고 가정하자. 

 

 

 

그렇다면 왼쪽의 그림과 같이 T(k)를 구하는 방법은 T(k-1)+T(k-2)일 것이다. 왜냐하면 타일을 세로로 한 개 세운 경우와 타일을 가로로 2개 쌓은 경우가 가능한 유일한 경우의 수이기 때문이다. 왜 세로로 2개는 없냐고 물을 수 있다. 그 경우는 반드시 타일을 세로로 한 개 세운 경우에 포함되기 때문에 굳이 고려해 줄 필요가 없는 것이다. 

 

 

 

시도 1(Python)

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * 1001
dp[0], dp[1], dp[2] = 1, 2, 3
if n<3:
    print(n)
else:
    for i in range(3, n):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[n - 1]%10007)

시도 2(C언어)

#include <stdio.h>
int main() {
    int n;
    int dp[1001];
    dp[0]=1,dp[1]=2,dp[2]=3;
    scanf("%d",&n);
    if(n<3) printf("%d",n);
    else{
        for(int i=3;i<n;i++)
            dp[i]=(dp[i-1]+dp[i-2])%10007;
        printf("%d",dp[n-1]);
    }
    return 0;
}