[BOJ] 2482 - 색상환 (Python)

 

 

아이디어

 

동적 계획법으로 서로 인접하지 않은 색을 고를 수 있는 경우의 수를 구한다.

 

 

풀이

 

def solution():
    N = int(input())
    K = int(input())
    p = 1000000003
    if K > N//2:
        print(0)
        return
    dp = [[0]*N for _ in range(N//2+1)]
    dp[1] = [1]*N
    for i in range(2, N//2+1):
        for j in range(N-3):
            dp[i][j+2] = (dp[i][j+1]+dp[i-1][j])%p
        dp[i][-1] = dp[i][-2]
    res = 0
    for j in range(N):
        res = (res+dp[K][j])%p
    print(res)

solution()