문제
색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다.
그림 1. 먼셀의 20색상환
색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다. 시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다.
주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보자. 먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 있게 10개의 색을 선택하는 경우의 수는 2이지만, 시각적 대비 효과를 얻을 수 있게 11개 이상의 색을 선택할 수 없으므로 이 경우의 수는 0이다.
주어진 정수 N과 K에 대하여, N개의 색으로 구성되어 있는 색상환 (N색상환)에서 어떤 인접한 두 색도 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 프로그램을 작성하시오.
입력
입력 파일의 첫째 줄에 색상환에 포함된 색의 개수를 나타내는 양의 정수 N(4 ≤ N ≤ 1,000)이 주어지고, 둘째 줄에 N색상환에서 선택할 색의 개수 K(1 ≤ K ≤ N)가 주어진다.
출력
첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다.
예제 입력 1
4
2예제 출력 1
2나의 풀이
DP문제로 N번째의 색을 사용하는지 안하는지를 생각해보는 것으로 시작하는 문제였습니다.
이 문제의 풀이는 우선 원형이 아닌 선형으로 모든 경우의 수를 구해주고나서 그 구해진 dp를 가지고 원형으로 이었을때의 경우의 수를 찾아내는 방법입니다.
그럼 우선 선형으로 인접하지 않는 것으로 k개를 선택하는 경우의 수를 구해보겠습니다. 여기서도 N번째의 색을 사용하는 경우, N번재의 색을 사용하지 않는 경우를 아래와 같이 생각해볼 수 있습니다.
- N번째 색을 사용하는 경우 => 앞의
N-2개의 색들 중k-1개를 선택하였음.- N번째 색을 사용하지 않는 경우 => 앞의
N-1개의 색들 중에서 k개를 모두 선택하였음.즉, 이를 기반으로 점화식을 세우면
dp[i][j] = dp[i-2][j-1] + dp[i-1][j]과 같은 것을 알 수 있습니다. 이제 이 점화식을 가지고 모든 경우의 수를 구할 수 있습니다.그러나 문제에서 요구하는 답은 원형으로 생각을 해야합니다. 원형의 경우 추가적으로 생각해야 할 것은 1번 색을 골랐다면 N번째 색을 고를 수 없다는 것입니다. 따라서, 다음과 같은 경우를 생각해볼 수 있습니다.
- N번째 색을 사용하는 경우 => 앞의
N-3개의 색들 중k-1개 선택- N번째 색을 사용하지 않는 경우 => 앞의
N-1개의 색들 중k개 선택2번 경우는 위의 선형일 때와 같지만 1번의 경우
N-2가 아닌N-3인 것을 확인해 볼 수 있습니다. 이는 N을 선택할때, 1번도 빼주어야하기 때문입니다. 이렇게 공식을 알았다면 앞선 선형일때의 점화식을 가지고 모든 경우의 수를 구하고 구해진 경우의 수 dp테이블에서 문제에서 원하는 원형의 n개에서 k개를 고르는 경우의 수인dp[N-3][K-1] + dp[N-1][k]가 바로 정답인 것입니다.
코드
# 2482번 색상환
n = int(input())
k = int(input())
dp = [[0] * (k+1) for _ in range(n+1)]
# dp 테이블 초기화
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):
dp[i][j] = (dp[i-2][j-1] + dp[i-1][j]) % 1000000003
answer = (dp[n-3][k-1] + dp[n-1][k]) % 1000000003 # 원형으로 생각할때의 경우의 수
print(answer)
