문제

풀이

1. n >= 3일 경우, dp[n] = dp[n-1] + dp[n-2]
2. 문제의 조건 때문에 결과를 15746으로 나눠줘야 함.(안하면 메모리 초과)

코드

def tile() :
    n = int(input())
    
    if n <= 2 :
        if n == 1 :
            return 1
        else :
            return 2
    else :
        dp = [0 for _ in range(n)]
        dp[0] = 1
        dp[1] = 2
        
        for i in range(2, n) :
            dp[i] = (dp[i-1] + dp[i-2]) % 15746
        
        return dp[-1]

print(tile())