2023년 11월 17일 알고리즘 문제풀이

문제

2 x n 타일링

난이도

Lv.2

코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def solution(n):
    dp = [0 for _ in range(60001)]
    x = 1
    while x <= n:
        if x == 1:
            dp[x] = 1
        elif x == 2:
            dp[x] = 2
        else:
            dp[x] = (dp[x-1] + dp[x-2])%1000000007
        x += 1 
    return dp[n]

많이 볼 수 있는 DP문제이다. 2 x n 일땐 이전 조합들을 합친 것만으로도 다음 갯수를 산출할 수 있어서 크게 어렵지 않다. 수가 커지기 때문에 나머지로 표시해야 한다는 사실을 잠시 잊었다..