[프로그래머스] 산 모양 타일링

https://school.programmers.co.kr/learn/courses/30/lessons/258705

1) 코드

def solution(n, tops):
    answer = 0
    
    a = [0]*(n+1)
    b = [0]*(n+1)
    
    MOD = 10007
    
    a[0] = 0
    b[0] = 1
    
    for i in range(1, n+1):
        if tops[i-1] == 1:
            a[i] = (a[i-1] + b[i-1]) % MOD
            b[i] = (2*a[i-1] + 3*b[i-1]) % MOD
        else:
            a[i] = (a[i-1]+b[i-1]) % MOD
            b[i] = (a[i-1]+2*b[i-1]) % MOD
            
    return (a[n]+b[n]) % 10007
       

2) 해설

• 케이스 분리를 잘해야 하는 문제이다
  -> a에는 다음 범위를 침범하는 한 가지 케이스가
  b에는 다음 범위를 침범하지 않는 세 가지 케이스가 각각 관리되며
  memoization을 활용해 누적적으로 값을 구해나간다