색상환

문제 링크

발상

구조상 첫 인덱스와 마지막 인덱스가 연결되어있는 환형 구조의 문제다. 볼록 다각형 대각선 긋기 문제로 치환해서 생각하면 조금 더 편하다. 볼록 다각형도 인접한 꼭짓점을 그어도 대각선이 생기지 않는다. 가능한 경우는 어떤 인덱스를 선택하냐/선택하지 않냐 2가지 경우 밖에 없다. 어떤 인덱스 $i$를 선택했다면 $i-1$, $i+1$은 선택이 불가능하다. 반대로 $i$를 선택하지 않았다면 $i$를 제외한 모든 인덱스를 선택할 수 있다. 즉, $i$의 선택 여부에 따라 두 가지 경우로 나눠 재귀 구조의 부분 문제를 형성할 수 있다. 문제를 재귀구조로 분할했으니 다음으로 기저사례를 찾아보자.

$$\{\begin{array}{l}n=\text{전체 인덱스 수}\\ k=\text{골라야하는 인덱스 수}\end{array}$$

서로 이웃하는 인덱스를 선택할 수 없으므로 비둘기집 원리에 의해 $\frac{n}{2}$를 초과하는 인덱스를 선택할 수 없다. 따라서 $2k>n$이면 경우의 수는 반드시 0이다. 다음으로 $k$가 $1$인 경우다. 이웃하는 경우가 없으므로 자명하게 경우의 수는 $n$이다.

점화식

$$\{\begin{array}{l}f(n,k)=\text{n개의 인덱스 중 k개의 인덱스를 선택하는 경우의 수}\end{array}$$ $$f(n,k)=f(n-2,k-1)+f(n-1,k)$$

$f(n-2,k-1)$은 어떤 인덱스 $i$를 선택한 경우이다. 이 때, 이웃한 2개의 인덱스는 선택이 불가능해지므로 전체 수 $n-2$ 중에서 이미 선택한 $i$를 제외한 $k-1$개의 인덱스를 선택하는 부분 문제가 발생한다. $f(n-1,k)$은 어떤 인덱스 $i$를 선택하지 않은 경우이다. 이 때는 별도의 인덱스 제외 없이 $i$를 제외한 모든 인덱스를 선택할 수 있으므로 전체 수 $n-1$개 중에서 다시 $k$개를 선택하는 부분 문제가 발생한다.

코드 ( Top-Down )

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int mod = 1e9 + 3;
vector<vector<int>> dp;
int r(int n, int k) {	
	if (dp[n][k] != -1) return dp[n][k];
	if (k * 2 > n) return dp[n][k] = 0;
	if (k == 1) return dp[n][k] = n;
	return dp[n][k] = (r(n - 2, k - 1) + r(n - 1, k)) % mod;
}
int main()
{
	int n, k; cin >> n >> k; dp = vector<vector<int>>(n + 1, vector<int>(k + 1, -1));		
	cout << r(n, k);
	return 0;
}

코드 ( Bottom-Up )

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 3;
int main()
{
	int n, k; cin >> n >> k;
	if (k * 2 > n) {
		cout << 0;
		return 0;
	}
	vector<vector<int>> dp = vector<vector<int>>(n + 1, vector<int>(k + 1));
	for (int i = 2; i <= n; i++) {		
		dp[i][1] = i;
		for (int j = 2; j <= i / 2; j++) {
			if (j > k) continue;
			dp[i][j] = (dp[i - 1][j] + dp[i - 2][j - 1]) % mod;
		}
	}
	cout << dp[n][k];
	return 0;
}