[백준]2482 색상환 #dp#grid

1.풀이

(1) 점화식

dp[i][j] : i개의 색 중 j개를 사용할 수 있는 경우의 수 (단 i<N)

i번째 색까지 j개 사용하는 경우의 수는 아래 두가지 경우를 합한 경우이다.

ㄱ. i-1번째까지 j개 사용하는경우(i번째 색을 사용하지 않는경우) : dp[i-1][j]

ㄴ. i-2번째까지 j-1개 사용하는 경우 (i번쨰 색을 사용하는 경우) : dp[i-2][j-1]

=> dp[i][j]=dp[i-1][j]+dp[i-2][j-1]

​

dp[N][K] : N개의 색 중 K개를 사용할 수 있는 경우의 수.

* i==N일때는 (원형이므로) 1번째 색깔이 칠해져있을때를 고려해주어야 한다.

ㄱ. N-1번째까지 K개 사용한 경우 : dp[N-1][k] (i(=N)번째 색을 사용하지 않는 경우) : dp[N-1][K]

ㄴ.1번째와 i-1번째가 색칠되어 있지 않는경우(i(=N)번째 색을 사용하는 경우) : dp[N-3][K-1]

=> dp[N][K]=dp[N-1][K]+dp[N-3][K-1]

​

(2) 초기조건

ㄱ. i개의 색 중 1개를 사용할 수 있는 경우는 항상 i개

ㄴ. i개의 색 중 0개를 사용할 수 있는 경우는 항상 1개

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

 

2. 소스코드

mod=1000000003
N=int(input())
K=int(input())

#dp[i][j] : i번째색까지 j개를 선택한 경우의 수
dp=[[0 for j in range(N+1)] for i in range(N+1)]

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

for i in range(2,N+1):
    for j in range(2,K+1):
        dp[i][j]=(dp[i-2][j-1]+dp[i-1][j])%mod

'''
for i in dp:
    print(i)
'''
print((dp[N-1][K]+dp[N-3][K-1])%mod)