아방가르드 타일링

import sys; sys.setrecursionlimit(1000000) cache = [-1] * 100001 cache[0] = 1 cache[1] = 1 cache[2] = 3 cumsumcache = [-1] * 100001 def cumulative(n): # solve(n) + solve(n-3) + .... if n < 0: return 0 if cumsumcache[n] != -1: return cumsumcache[n] cumsumcache[n] = solve(n) + cumulative(n-3) return cumsumcache[n] def solve(n): if n < 0: return 0 if cache[n] != -1: return cache[n] v = 0 v += solve(n-1) * 1 v += solve(n-2) * 2 v += solve(n-3) * 1 v += 4 * cumulative(n-3) + 2 * cumulative(n-4) + 2 * cumulative(n-5) cache[n] = v % 1000000007 cumsumcache[n] = cache[n] + cumsumcache[n-3] return cache[n] def solution(n): return solve(n)