[Level 3] 2xn 타일링

programmers.co.kr/learn/courses/30/lessons/12900?language=python3

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

---

접근

백준에서도 풀어봤던 문제다.

그런데 dp로 접근했을 때 시간초과가 발생하였고 다른 사람의 풀이를 참고하였다.

 

구현

현재 n의 경우의 수는 n-1, n-2의 경우의 수와 같은데 아래와 같이 구현할 수도 있다는 것을 알았다.

dp1에는 현재 n의 경우의 수에 해당하고 dp2는 다음 n의 경우의 수가 담기게된다.

def solution(n):
    answer = 0
    dp1, dp2 = 1, 1
    for _ in range(n):
        dp1, dp2 = dp2, dp1+dp2
    answer = dp1%1000000007
    return answer