백준 2482 색상환

haruponea·2021년 4월 10일
0

BOJ

목록 보기
41/41

문제 링크 https://www.acmicpc.net/problem/2482

풀이
원형으로 되어있어서 조심해야하는 부분이 있는 문제였습니다. dp[i][j]를 i번째 색까지 고려하여 총 j개를 선택했을 때 나오는 경우의 수라고 정했습니다. dp[i][j]에서 i번째 색을 선택하면 i-1번째를 선택하지 못하므로 i-2개의 색 중에서 j-1개를 선택하는 경우와 같습니다. i번째 색을 선택하지 않을 때는 i-1개 색중에서 k개를 고르는 경우의 수와 같습니다. 따라서 점화식은 다음과 같습니다.
dp[i][j] = dp[i-1][j] + dp[i-2][j-1]
하지만 i==N일때는 위와 다릅니다. N번째 색을 고른다면 N-1, 1번째 색을 고르지 못하므로 N-3개의 색 중에서 j-1개를 고르는 경우의 수와 같습니다. 또한 N번째 색을 고르지 않는다면 1 ~ (N-1)까지의 색 중에서 j개를 경우의 수와 같습니다. 따라서 i=N일때 점화식은 다음과 같습니다.
dp[i][j] = dp[i-3][j-1] + dp[i-1][j]

Python

import sys
input = sys.stdin.readline
mod = 1000000003
n = int(input())
k = int(input())
dp = [[0]*(1002) for _ in range(1002)]
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):
        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])

0개의 댓글