python 2 x n 타일링

처음에는 순열의 합으로 접근하였다.

 

순열의 합 코드

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

 

 

그러나 실행 결과도 이상하고(아직도 이유를 모르겠다. n = 16 부터 값이 1씩 작게 나옴) 대부분은 런타임 에러가 났기 때문에 이러한 접근이 아니라고 빠르게 캐치했다.

그리고 실행 결과를 쭉 보다 보니 익숙한 수열... 피보나치였다.

 

순열의 합보다 훨씬 단순하게 접근이 가능했다. 이해하기도 훨씬 단순했다.

메모리 사용을 최소화 해야 마지막 효율성 테스트를 통과할 수 있었다.

 

최종 코드

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