[Python] 백준 2482번: 색상환

https://www.acmicpc.net/problem/2482

2482번: 색상환

1. 처음과 마지막이 (0, 0), (0, 1), (1, 0), (1, 1) 일때로 나누었다.

(0, 0) 이면 dp[i][j-1]가 0으로 끝날때 + 0

(0, 1) 이면 dp[i-1][j-1]의 (0, 0)에 + 1, 

(1, 0) 이면 dp[i][j-1]가 1로 시작할때 + 0

(1, 1) 이면 dp[i-1][j-1]의 (1, 0)에 + 1

마지막에 (1, 1)인 경우만 제외하고 전부 더해준다.

import sys
input = sys.stdin.readline

mod = int(1e9+3)
n = int(input())
k = int(input())
dp = [[[0, 0, 0, 0] for _ in range(n+1)] for _ in range(k+1)]

for i in range(2, n+1):
    dp[1][i] = [i-2, 1, 1, 0]

for i in range(2, k+1):
    for j in range(i*2-1, n+1):
        dp[i][j][0] = (dp[i][j-1][1] + dp[i][j-1][0]) % mod
        dp[i][j][1] = dp[i-1][j-1][0] % mod
        dp[i][j][2] = (dp[i][j-1][2] + dp[i][j-1][3]) % mod
        dp[i][j][3] = dp[i-1][j-1][2] % mod

print(sum(dp[k][n][:3]) % mod)