[PG/Python] 2 x n 타일링

📌 문제

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

코딩테스트 연습 - 2 x n 타일링

 

📌 문제 접근 방법

1. n이 1일 때부터 경우의 수를 모두 계산해보니 점화식이 f(n) = f(n-1) + f(n-2)가 나왔다.
2. 위의 식을 피보나치 수열이라고 하는데, 이를 재귀로 구현할 경우 시간이 오래걸리기 때문에 메모이제이션을 사용해서 풀이했다.
3. 하지만 시간초과가 나서 질문하기를 살펴보니, 나는 매번 연산을 하는게 시간이 오래걸릴거라고 생각해서 리스트에 모든 값을 저장하고 마지막 n번째만 1000000007로 나누었는데 이것보다 큰 수들간의 연산이 더 시간이 오래걸린다고 한다. 그래서 리스트에 값을 저장할 때마다 나누어서 나머지만 저장했더니 효율성까지 통과하였다.
4. 점화식 도출과정을 좀 더 찾아보니 https://wwlee94.github.io/category/algorithm/dp/2xn-tiling/ 여기 블로그가 잘 설명되어있는 것 같다!

 

📌 코드

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