https://www.acmicpc.net/problem/11726 2*n 타일링 python

approach.txt

문제의 조건
2 x 1(세로) 타일과
1 x 2(가로) 타일을 사용해 
2 x n 타일을 채워라

1 x 2 를 사용시 1 x 2를 한 번더 사용해야하므로 2개를 1개로 취급 

타일의 크기가 n 일 때 세로 타일은 n칸에서 1칸을 차지 -> n-1 
  n-1    1
---------
        | |
        | |
---------
     n

타일의 크기가 n 일 때 가로 타일은 n칸에서 2칸을 차지 -> n-2 
  n-2    2
-----------
       |    |
        ----
       |    |
-----------
     n

즉, 왼쪽에 뭐가 붙을지 모르지만 오른쪽에 세로가 붙거나 가로가 붙으면 조합을 완성할 수 있음.
2 x 1때는 세로 한 칸으로 정하고 이걸 불러와서 2 x 2세로 한 칸 붙이는 식으로,
가로 붙일 때는 2 x 0때 불러오고 가로를 붙임 -> DP를 사용한다.

그림
--                 ---- 
| |               |----|
-- 는 세로,        ----   는 가로

없음(2x0)    *d[0] = 1                                                n=0 -> 1
-- 
| |                                                                   n=1 -> 1
--
--           --                       ----
| |     +    | |          없음    +  |----|                            n=2 -> 2
--           --                       ----
--  --       --               ----        --        --       ----
| |  | |  + | |               |----|  +  | |        | |  +   |----|   n=3 -> 3
--  --       --               ----        --        --       ----      

그림 설명
2x1에서는 2x0(n-1)을 불러와서 세로를 추가한다.
2x2에서는 2x1(n-1)을 불러와서 세로를 추가한 후, 2x0(n-2)을 불러와서 가로를 추가한다.
2x3에서는 2x2(n-1)을 불러와서 세소를 추가한 후, 2x1(n-2을 불러와서 가로를 추가한다.

baekjoon11726.py

#top-down
#@warning recursion depth can be over 992 
d = [0] * 1001
def f(n):
    if n <= 1:
        return 1
    if d[n] > 0:
        return d[n]
    d[n] = f(n-1) + f(n-2)
    d[n] %= 10007
    return d[n]


print(f(int(input())))

#bottom-up
def f(n):
    d = [0] * (n+1)
    d[0] = 1
    d[1] = 1
    for i in range(2, n+1):
        d[i] = d[i-1] + d[i-2]
        d[i] %= 10007
    return d[n]


print(f(int(input())))