[AlgoSpot] 알고스팟 > TILING2🖼 > Python 문제풀이!

<알고스팟 문제풀이>

---

해답)

tile = [-1 for _ in range(101)]


def TILING2(n):
    if tile[n] != -1:
        return tile[n]
    if n < 0:
        return False
    if n == 1:
        return 1
    if n == 2:
        return 2
    tile[n] = TILING2(n-1) + TILING2(n-2)
    return TILING2(n-1) + TILING2(n-2)


testcaseNum = int(input())
for _ in range(testcaseNum):
    answer = TILING2(int(input())) % 1000000007
    print(answer)

 

풀이)

길이가 1일때 만들 수 있는 타일의 개수 : 1개

길이가 2일때 만들 수 있는 타일의 개수 : 2개

길이가 3 이상일 때 : 길이가 1일때 만들 수 있는 타일 수 + 2일 때 만들 수 있는 타일 수

...

길이가 k 일 때 : 길이가  k-1 일 때 만들 수 있는 타일 수 + k-2일 때 만들 수 있는 타일 수

 

시간초과로 인해 캐싱이 필요하다. (동적 계획법)

 

 

* 문제의 저작권은 알고스팟에 있습니다.