백준 2482번: 색상환 (Python)

접근

원형이 아닌 직선에서 선택하는 경우를 먼저 생각한 후, 이를 원형으로 확장하였다.

dp[i][j] = i개의 색 중에 j 개의 색을 선택하는 경우의 수

라고 지정하고 dp 문제를 풀어보았다.

dp[i][j] 에서 i 번째 색을 선택하면 i - 1 번째 색을 선택하지 못하므로 i - 2 개의 색 중에서 j - 1 개의 색을 선택하는 경우의 수와 같다. i 번째 색을 선택하지 않으면 i - 1 개의 색 중에서 j 개의 색을 선택하는 경우의 수와 같다. 이를 더하면 다음과 같은 점화식을 얻을 수 있다.

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

하지만 i == n 일 경우, n 번째 색을 고른다면, n - 1 번째 뿐만 아니라 1번째 색도 선택하지 못하므로 i - 3 개의 색 중에서 j - 1 개의 색을 선택하는 경우와 같다.

$$ dp[i][j] = dp[i - 3][j - 1] + dp[i - 1][j] $$

이를 코드로 표현하면 아래와 같다.

코드

import sys

mod = 1000000003
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())

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])

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!