Baekjoon 2482. 색상환 / Python

알고리즘 설명

문제 설명

주어진 n개의 색상환에서 서로 인접하지 않는 색을 k개 선택해야 한다.

코드 설명

dp를 2차원 배열로 만든다.
dp[i][j] 는 i개의 색상에서 j개의 색을 선택하는 경우의 수를 뜻한다.
다음으로 넘어가는 경우 색을 선택하지 않은 경우 dp[i-1][j], 선택한 경우 dp[i-2][j-1]을 이용할 수 있다.
dp[i][0] : 0개의 색을 선택하는 경우는 항상 1이고,
dp[i][1] : i개의 색에서 1개의 색을 선택하는 경우는 항상 i이다.

시간복잡도 : O(n * k)

MOD = 1000000003

n, k = int(input()), int(input())

# k > n // 2인 경우 결과는 항상 0
if k > n // 2:
    print(0)
    exit(0)

# DP 테이블 초기화
dp = [[0] * (k + 1) for _ in range(n + 1)]

# 초기 상태
for i in range(n + 1):
    dp[i][0] = 1  # 0개의 색을 선택하는 경우의 수는 1입니다.

# DP 테이블 채우기
for i in range(1, n + 1):
    for j in range(1, k + 1):
        if i - 2 >= 0:
            dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % MOD
        else:
            dp[i][j] = dp[i - 1][j] % MOD

# 결과 출력
print((dp[n - 3][k - 1] + dp[n - 1][k]) % MOD)