[백준][DP] 2482.색상환

2482.색상환

 

• 풀이
  • dp[i][j] = i개 중에 j개 선택된 경우 ( i 까지 중에 j개로 생각하면 안됨! )
    • n번째 값 선택한 경우 = 첫번째 값 선택하지 않은 경우
      • n-3개 중에 k-1개 선택
      • n-2가 아닌 n-3개인 이유: n을 선택했으니까 (n-1, n, 1)빼고 n-3개중에 k-1개 선택
    • n번째 값 선택 안하는 경우
      • n을 빼니까
      • n-1개 중에 k개 선택

mod = 1000000003

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

for i in range(n+1):
    dp[i][0] = 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-3][j-1]+dp[i-1][j]) % mod
        else:
            dp[i][j] = (dp[i-2][j-1] + dp[i-1][j]) % mod


print(dp[n][k])