[BOJ] 2482번 - 색상환

[BOJ] 2482번 - 색상환

 

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

2482번: 색상환

 

알고리즘

---

연속되어 있는 색은 추가가 불가능

단계별 갯수를 세가면서 추가 -> DP

DP를 나타낼 때 DP[i][j] 시 i는 색의 갯수 / j는 색을 고를 수 있는 경우이다.

 

1. i가 1인 경우에는 모두 n의 갯수에 맞추어 증가한다.

2. 후에 i가 2부터는 경우의 수를 나타내다 보면 DP[i][j] = DP[i-1][j-2] + DP[i][j-1] 로 계산식이 되는 것을 알 수 있다.

3. 시작하는 지점은 K*2인 경우부터 시작하게 된다.

4. 이를 반복

 

코드

---

#BOJ 2482번

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

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

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

print(dp[-1][-1]%devide)