2xn 타일링(파이썬)

Posted on Edited on In , ,

문제정의

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있다. 이 타일로 2*n바닥을 덮을 수 있는 경우의 수를 구하는 문제이다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
def solution(n):
    answer = 0

    fn, fn_1 = 0, 1
    for i in range(n+1):
        fn, fn_1 = fn_1, fn+fn_1
        fn %= 1000000007
        fn_1 %= 1000000007

    return fn % 1000000007

print(solution(4))
자바로 풀 때보다 코드가 한결 간결하다. 이 문제를 잘 생각해보면 피보나치 수열과 원리가 같다는 것을 알 수 있다. 자바로 풀 때는 재귀로 풀었었는데, 파이썬은 반복을 통해서 구현하였다.

시간 복잡도는 \(O(n)\)이다.

테스트


테스트 화면