알고리즘 문제

백준 2482번 : 색상환 in Python

YJH3968 2021. 6. 11. 20:20
728x90
2482번: 색상환
 
www.acmicpc.net

이 문제는 N개의 색으로 구성된 색상환에서 어떤 인접한 두 색도 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 문제이다.

이는 조합을 dynamic programming으로 구하는 방법을 활용한다. 예를 들어 서로 다른 N개의 대상 중 순서없이 K개를 선택하는 경우의 수를 구할 때는 첫 번째 대상을 포함하느냐 포함하지 않느냐에 따라 두 가지 경우로 나누고, 포함하는 경우는 N-1개 중 K개를, 포함하지 않는 경우는 N-1개 중 K-1개를 택하는 경우이므로 두 조합의 경우의 수를 더해서 구할 수 있다.

이 문제도 위와 유사한 형태지만 몇몇 조건이 추가되어 이를 고려해야 한다. 색상환에서 마지막 색을 제외한 상태에서 경우의 수를 구했다고 가정해보자. 그러면 첫 번째 색과 (N-1)번째 색이 이웃하므로 두 색 모두 선택되는 경우는 고려되지 않는다. 이때 마지막 색을 넣으면 모든 경우는 마지막 색과 이웃한 첫 번째 색과 (N-1)번째 색 중 적어도 하나는 선택되지 않는다. 그러므로 고려해야 할 경우는 마지막 색이 선택된 경우와, 첫 번째 색과 (N-1)번째 색이 동시에 선택된 경우이다. 이 경우는 마지막 색과 첫 번째 색을 제외한 상태에서 (K-1)개의 색을 선택하는 경우를 구한 뒤, (N-1)번째 색이 선택된 경우 첫 번쨰 색을 선택하고, 그렇지 않은 경우에는 마지막 색을 선택한다. 

이렇게 하는 것이 가능한 이유는 두 가지 경우로 나눠 설명할 수 있다. 마지막 색을 선택한 경우는 2개의 색을 제거했을 때 (N-1)번째 색을 제외한 나머지 색을 (K-1)개 선택하는 경우와 같기 때문이다. 그리고 첫 번째 색과 (N-1)번째 색이 동시에 선택된 경우는 2개 색을 제거했을 때 (N-1)번째 색을 포함해 (K-1)개의 색을 선택하는 경우와 같기 때문이다. 특히 이 경우는 (N-1)번째 색을 선택하면 두 번쨰 색을 동시에 선택할 수 없기 때문에 첫 번째 색을 선택하는 것이 가능하다.

그러므로 이를 정리하면 N(>1)개의 색상환에서 서로 다른 K(>1)개의 색을 선택하는 경우의 수는 N-1개의 색생환에서 K개의 색을 선택하는 경우의 수와 N-2개의 색상환에서 K-1개의 색을 선택하는 경우의 수를 합하면 되고, K=1이고 N>1일 때 경우의 수는 N과 같으므로 이를 base case로 한다.

이를 코드로 구현하면 다음과 같다.

N = int(input())
K = int(input())
dp = [[0]*(K+1) for _ in range(N+1)]
# base case를 설정한다.
for i in range(2, N+1):
    dp[i][1] = i
for i in range(2, N+1):
    for j in range(2, K+1):
        dp[i][j] = dp[i-1][j] + dp[i-2][j-1]
print(dp[N][K]%1000000003)
728x90