https://jungol.co.kr/problem/2264
| 시간 제한 | 메모리 제한 |
| 1초 | 64MB |
문제
색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다.
미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다.
아래 그림은 먼셀의 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) 으로 나눈 나머지를 출력한다.
풀이
$i$번째 색깔을 골랐다면 $i+1$번째 색깔은 고를 수 없습니다. 3차원 리스트로 `dp`테이블을 관리할 수 있습니다.
dp[i][j][k] = $i$번째 색깔까지 $j$개의 색깔을 고르는 방법의 수
$k$가 1이면 $i$번째 색깔을 선택한 경우, 0이면 $i$번째 색깔을 선택하지 않은 경우
다만 이 문제에서 색상환은 고리형태라서 첫 번째 색상과 마지막 색상이 연결되어있습니다. 첫 번째 색깔을 골랐다면 두 번째 색깔만 고를 수 없는 게 아니라 마지막 색깔도 고를 수 없게 됩니다. 그래서 첫 번째 색깔을 고른 경우에 대해 $N$개의 색깔을 모두 탐색하고 마지막 색깔을 고르지 않은 경우만 확인하고, 첫 번째 색깔을 고르지 않은 경우에 대해 다시 $N$개의 색깔을 모두 탐색하고 마지막 색깔을 고른 경우와 고르지 않은 경우 모두를 확인하면 됩니다.
`dp`테이블의 점화식은 다음과 같습니다.
dp[i][j][0] = (dp[i-1][j][1] + dp[i-1][j][0]) % 1000000003
dp[i][j][1] = dp[i-1][j-1][0]
정답 코드
n = int(input())
k = int(input())
mod = 1_000_000_003
dp = [[[0] * 2 for _ in range(k+1)] for _ in range(n)]
# 첫 번째 색깔을 고르는 경우와 고르지 않는 경우로 나누어서
# dp 테이블 초기값 설정
for i in range(1, n):
for j in ranage(min(i, k) + 1):
dp[i][j][0] = (dp[i-1][j][1] + dp[i-1][j][0]) % mod
if j > 0:
dp[i][j][1] = dp[i-1][j-1][0]
