2 x n 타일링

https://programmers.co.kr/learn/courses/30/lessons/12900#

세로가 2로 고정이 되어있기 때문에, 타일로 만들 수 있는 조합의 수는 2개로 제한되어 있다.
1) 단순히 세로로 하나 세워서 만들 수 있는 경우 ( l )
2) 가로로 두개를 쌓아서 만들 수 있는 경우 일 (대략 이런 모양 ->日)

2번째 경우의 수를 0부터 n // 2까지 증가시키며 순서만을 고려하여 합하였다.

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return(result)
        

def combination(n,m):
    if m == 0:
        m = n
    return factorial(n) // (factorial(m) * factorial(n - m))

def solution(n):
    answer = 0
    
    for i in range(n//2 + 1):
        a = i
        b = n - 2 * a
        answer += combination(a + b, b)
        
    return answer % 1000000007

시간초과가 몇가지 나와 버렸다....
해당 알고리즘으로 경우의 수를 펼쳐보았더니, 피보나치 수열의 형태가 보였다...
n = 1 -> 1개
n = 2 -> 2개
n = 3 -> n = 1에서의 모양과 n =2에서의 모양이 모두 나타남.
(1 + 2) 개 = 3개

def solution(n):
    answer = 0
    tmp = [0 for i in range(n)]
    tmp[0] = 1
    tmp[1] = 2
    for i in range(2, n):
        tmp[i] = (tmp[i - 1] + tmp[i - 2]) % 1000000007
    answer = tmp[i]
    return answer % 1000000007