title: "[프로그래머스] 아방가르드 타일링 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/181186"
description: "프로그래머스 Level 3 문제 [아방가르드 타일링]의 풀이를 정리합니다."
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)
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges