[python] 백준 2482 색상환

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

2482번: 색상환

 

문제해결

 

• 원 안에서 이웃하지 않게 k개의 색을 고르는 문제 ( 원 순열은 아니고 원 조합도 아니고... 조건있는 원조합?)
• 규칙을 찾기는 어렵다.
• 1개 고를 때 부터 하면 n개의 색이 있는 경우 1개를 고르는 방법은 n가지 이다.
• 0개 고르는 방법은 1가지라고 하자.
• n개의 색이 있을 때 n-1까지 임의의 수 i는 i-1과 i+1의 색을 보면 되고 n은 n-1 1의 색을 봐야한다.
• dp[i][j]를 n개의 색중 1부터 i까지 볼 때 j개의 색을 고르는 경우라고 하자. 그러면 i가 색칠되었을 때 i-1은 색칠 되지 않아야하며(i+1도 색칠 안되야하지만 i까지 보는 것이므로 생각x) dp[i-2][j-1]가지 경우가 있고 i가 색칠되지 않았을 때 dp[i-1][j]가지 경우의 수의 합과 같다. 즉 dp[i][j] = dp[i-2][j-1] + dp[i-1][j]
• i가 n이면 다르다. n은 끝부분이므로 1도 생각해야 한다. 즉 dp[n][j] = dp[n-3][j-1] + dp[n-1][j] 이다.

 

CODE

mod = 1000000003
n = int(input())
k = int(input())
dp = [[0]*(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]
        else:
            dp[i][j] = dp[i-1][j] + dp[i-2][j-1]
        dp[i][j] %= mod
print(dp[n][k])