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