2022.06.05 [프로그래머스] (python 파이썬) 2Xn 타일링

 

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

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

 

---

풀이

 

이 문제는 우선 규칙을 찾는 것이 먼저라고 생각들었다. 그래서 아래와 같이 일정 수까지 직접 구해보았다.

1	1
2	2
3	3
4	5
5	8
6	13
7	21
8	34
9	55

위의 표를 보면 2Xn의 크기를 타일링 하는 가지수는 (n-1) + (n-2)인것을 확인할 수 있다.

위에서 찾은 방법을 코드로 옮기면 아래와 같다.

 

import sys
sys.setrecursionlimit(60000)
 
def solution(n):
 
    arr=[-1]*60001
    arr[0]=0
    arr[1]=1
    arr[2]=2
    
    def tail(a):
        if arr[a]!=-1:
            return arr[a]
        arr[a]=(tail(a-1)+tail(a-2))%1000000007
        return arr[a]
    
    return tail(n)