백준, boj) 2482. 색상환 ( C / C++ )

1. 문제 링크

https://www.acmicpc.net/problem/2482

2482번: 색상환

 

2. 문제 개요

 주어진 색상환의 인접한 색을 고르지 않는 것처럼 인접한 두 색을 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 프로그램을 작성하자.

 

 

3. 문제 힌트

dp문제이다.

dp를 [n][k]로 설계하고, n은 현재 고를 수 있는 색의 수, k는 이때까지 고른 색의 수로 정의하자.

 

 

4. 문제 풀기

인접한색을 선택하는 경우는 dp를 계산하면서 배제하기 때문에,

3차 배열을 만들어서 마지막 색을 선택했는지 구분할 필요가 없다.

왜 이얘기를 하냐면....

처음에 dp를 알맞게 설계했다.

밑의 코드에서도 똑같이 구현했지만

 

dp[n][k] = dp[n-2][k-1] + dp[n-1][k] (mod....)로 설계했다.

현재 상태는 2칸 전에서 1개를 색칠한 상태에서 올 수 있고, 이전 상태에서 색칠을 안 한 상태로 올 수 있다.

 

그런데 기저 경우가 가장 중요하다.

처음에 기저를 잘못 생각해서 뻘짓을 2시간남짓 했다..

다음날 뇌를 비우고 다시 5분 만에 한...

 

우선 설계한 dp 식에 의하면, k는 그대로고 n만 감소하는 경우가 있다.

따라서 n과 k의 관계를 나타낸 가정문이 필요하다.

 

i) k == 1이라면, n개만큼 선택할 수 있다.

ii) n == 0 | n < 2*k 이면 0을 반환해야 한다.  0개에서 k개를 선택하는 건 말이 안 되고, n <2*k라면 무조건 인접한 경우가 한 가지는 나오기 때문이다.

 

이점 고려해서 구현하자.

 

5. 코드

#include <cstdio>
#include <cstring>
using namespace std;

int dp_table[1001][1001];
int n, k;

int dp(int cur, int x)
{
	if (cur <= 0 || cur < 2 * x) return 0;
	if (x == 1)	return cur;

	int &cache = dp_table[cur][x];
	if (cache != -1)	return dp_table[cur][x];

	return cache = (dp(cur - 2, x - 1) + dp(cur - 1, x)) % 1000000003;

}

int main() 
{
	scanf("%d", &n);
	scanf("%d", &k);
	memset(dp_table, -1, sizeof(dp_table));

	printf("%d", dp(n, k));
	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~