전형적인 DP 문제

처음에는 밑 삼각형들에 대한 DP table로만 만드려다가, 윗 삼각형들에 대한 정보가 필연적으로 필요함을 깨닫고, 홀짝으로 구분하여 DP table만들어서 구현

전형적인 DP + 삼각형 추가 여부에 따른 조건 분기만 추가

MOD=10007
def solution(N, tops):
    DP=[0]*(2*N+1) # DP[x] : x 삼각형을 덮는 경우의 수
    DP[0]=1
    if tops[0]:
        DP[1]=3
    else:
        DP[1]=2
    for i in range(2,2*N+1):
        if i%2==0: # 짝수 -> 아랫변
            DP[i]=(DP[i-1]+DP[i-2])%MOD
        else: # 홀수 -> 윗변
            # top이 있으면
            if tops[(i-1)//2]:
                DP[i]=(DP[i-1]*2+DP[i-2])%MOD
            else:
                DP[i]=(DP[i-1]+DP[i-2])%MOD
    
    return DP[2*N]

참고로, 백준 풀면서 체화한 방식인

DP[i] = (DP[i-1]*2 + DP[i-2]) % MOD

MOD 연산을 바로바로 해주는거 꼭해야함. 안하면 시간초과

모듈러 연산에 대한 합동

(a + b) mod M = ((a mod M) + (b mod M)) mod M (a × b) mod M = ((a mod M) × (b mod M)) mod M