2482_색상환

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

2482번: 색상환

 

 

dp를 2차원배열로 설정해서 풀 수 있다.

 

dp[i][j]라면 i개의 색중에서 j개의 색을 선택하는 것이다.

 

dp를 채워나간다고 생각해보자.

 

만약 dp[i][j]를 채운다고 생각해보자.

 

i번째 색이 새로 추가되었다면 그 색을 칠하는 경우와 안 칠하는 경우 2가지가 나올 것이다.

 

만약 색이 추가되었다면 i-1번째색은 칠할 수 없고, 이때 색을 칠한다면 j-1개를 구해야 하므로

 

i-2 개의 색으로 j-1개의 색을 칠하는 경우와 같을 것이다.

색을 칠하지 않는다면, i-1개의 색으로 j개의 색을 칠하는 경우와 같다.

 

이때 만약 i가 n이라면 i-1뿐 아닌, 맨 처음색도 고를 수 없으므로 i-3개와 골라야 한다!

 

import sys

n = int(input())
k = int(input())

dp = [ [0] * (k + 1) for _ in range(n+1) ]

for i in range(n+1):
    dp[i][1] = i

for i in range(2,n+1):
    for j in range(2,k+1):
        if i!=n:
            dp[i][j] = dp[i-2][j-1] + dp[i-1][j]
        else:
            dp[i][j] = dp[i-3][j-1] + dp[i-1][j]
        dp[i][j] %= 1000000003
print(dp[-1][-1])