728x90
def solution(n, tops):
answer = 0
div = 10007
# 우하단 마름모를 제외한 경우의 수 배열
a = [0] * (n + 1)
# 우하단 마름모만을 포함하는 경우의 수 배열
b = [0] * (n + 1)
a[0] = 1
for i in range(0, n):
# 현재 순회 중 top 존재 시 발생 경우의 수 확인
if (tops[i] == 1):
a[i + 1] = a[i] * 3 + b[i] * 2
else:
a[i + 1] = a[i] * 2 + b[i] * 1
# 현재 정삼각형에서 우하단 마름모인 경우는 앞선 경우의 수와 무관
b[i + 1] = a[i] + b[i]
a[i + 1] = a[i + 1] % div;
b[i + 1] = b[i + 1] % div;
return (a[n] + b[n]) % div
