Boj 2482) 색상환

문제

백준 2482

방법 1 (BottomUp)

설명

dp[k][n] 은 [1, n] 까지의 색중에 k 개의 색을 뽑는 경우의 수라고 하자. 점화식은 dp[k][n] = dp[k][n-1] + dp[k-1][n-2] 가 된다. 왜냐하면 dp[k][n] 을 두가지 경우로 나눌 수 있기 때문이다.

• n 번째 색을 포함한다면 인접한 색을 건너뛰어 n-2 까지 k-1 개의 색을 선택해야한다.
• n 번째 색을 포함하지 않는다면 n-1 까지 k 개의 색을 선택해야한다.

이때 처음과 끝이 이어지는 경우를 제외시켜야 한다. 이는 처음과 끝이 이미 선택된 경우의 수를 빼는 방식으로 처리할 수 있다. 처음과 끝이 이미 선택하고, 그 양 끝에 공백을 보장해야하므로 공간 2개를 더 빼서, 총 dp[k-2][n-4] 를 빼야한다. 이때 뺄때 나머지 연산을 하므로 MOD 를 더하는걸 잊지말자.

시간 복잡도

O(\(\log{NK}\))

코드

const int MOD = 1000000003;
int dp[1001][1001];

int main()
{
	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; i++) dp[1][i] = i;

	for (int i = 2; i <= k; i++)              // k 개 뽑음
		for (int j = i * 2 - 1; j <= n; j++)  // j 번째 이하에서 뽑음
			dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 2]) % MOD;

	// 처음과 끝이 이어지는 경우 방지
	if (k > 2)  
		dp[k][n] = (dp[k][n] - dp[k - 2][n - 4] + MOD) % MOD;
	else if(k == 2)
		dp[k][n] = (dp[k][n] - 1 + MOD) % MOD;

	cout << dp[k][n];
}

방법 2

설명

선형으로 DP 를 돌릴 때 맨 앞과 뒤가 모두 선택되는 경우를 더 쉽게 제거하는 방법이 있다.

바로 1010 ... 패턴과 10 ... 01 패턴은 자유롭게 둘 수 있는 공간이 둘다 n-4 으로 똑같다는 것을 이용하는 것이다. 다시말해 바로 맨 앞과 뒤가 모두 선택되는 경우의 수는 첫번째와 세번째를 반드시 선택한 경우의 수와 똑같은데, 1010... 패턴을 제외하는 것이 더 간편하므로 이쪽을 제외하는 것이다.

이를 적용하기 위해선 방법 1에서 약간만 수정하면 된다. 아래 코드처럼 2*i-1 이 아닌 2*i 부터 점화식을 돌려도 되고, dp[1][1] = 0 으로 해둬도 된다.

코드

const int MOD = 1000000003;
int dp[1001][1001];

int main()
{
	int n, k;
	cin >> n >> k;

	for (int i = 0; i <= n; i++) dp[1][i] = i;

	for (int i = 2; i <= k; i++)              // k 개 뽑음
		for (int j = i * 2; j <= n; j++)      // j 번째 이하에서 뽑음
			dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 2]) % MOD;

	cout << dp[k][n];
}

방법 3

설명

방법 2의 점화식인 dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 2] 에서 우변의 i 를 i-1 로 바꾸면 dp[][] 의 차원이 하나 필요없어진다.

이는 dp[i][j-1] => dp[i][j-2] + dp[i-1][j-3] 으로 풀어쓸 수 있는 것을 생각해, dp[i] 를 사용하는 항을 dp[i-1] 로 계속 바꾸면 된다. 그러면 점화식은 다음과 같다.

\[\mathrm{dp}_{i+1}[j] = \sum_{t=i \times 2}^{j}{\mathrm{dp_{i}[t-2]}}\]

이는 먼저 누적합을 수행 한 후에 , 꺼내 올 때 \(-2(i-1)\) 만큼 오프셋을 취하는 방식으로 구현할 수 있다.

이때 아래코드는 of 를 두어 2*i 부터 더하는게 아니라 2 부터 더할 수 있도록 해주었다.

코드

const int MOD = 1000000003;
int dp[1003];

int main()
{
	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; i++) dp[i] = i;

	for (int i = 2; i <= k; i++)                      // k 개 뽑음
		for (int j = i * 2, of = j-4; j <= n; j++)    // j 번째 이하에서 뽑음
			dp[j - 1 - of] = (dp[j - 1 - of] + dp[j - 2 - of]) % MOD;

	// k 가 n*2 보다 큰 경우는 dp 가 업데이트 안된채로 남아있으므로 예외
    cout << (k * 2 <= n ? dp[n - (k-1)*2] : 0);             
}