[백준/C++] 색상환 (No. 2482)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 저번에 풀었던 RGB거리 2와 사실 크게 다르지 않은 문제다

 

단지 차이점이 있다면, 저번 문제에서는 가중치를 구해야 했다면, 이번 문제는 경우의 수를 구하는 것이다.

 

문제의 핵심은 색을 칠하기 위해서 i번째 색을 선택하면 i-1번째 색과 i+1번째 색을 선택할 수 없다는 것이다.

 

그러므로 i-1번째 색을 사용했다면, i번째 색을 사용할 수 없고 i-1번째 색을 사용하지 않았다면 i번째 색을 사용할 수 ㅣㅆ다는 점을 이용해 N번째 색에 도달할 동안 몇 개의 색을 선택했는지 저장하며 문제를 풀면 된다.

 

여기서 중요한 점은 N번째 색에 도달했을 때 현재 몇 개의 색을 칠했는지 알고 있어야 한다는 점이다.

그리고 어차피 K개의 색을 선택하는 경우를 구하는 게 목적이므로 K개 이상의 색을 선택하는 경우는 고려하지 않아도 된다.

 

그러므로 이러한 점을 고려하면 다음과 같이 DP배열을 만들고 점화식을 만들 수 있다.

 

DP[현재 색 선택여부][현재까지 선택한 색의 수][현재 탐색하고 있는 색의 순번]으로 정의하면

 

DP[j번째 색을 선택 O ][ i ][ j ] = DP[j-1번째 색을 선택 X ][ i -1 ][ j -1]

DP[j번째 색을 선택 X ][ i ] [ j ] = DP[j-1번째 색을 선택 X ][ i ][ j - 1 ] + DP[j-1번째 색을 선택 O ][ i ][ j-1]

 

위와 같이 표현할 수 있다.

 

이제 DP배열의 점화식을 구했으므로 마지막으로 처리해야할 예외가 있다.

 

1번째 색을 선택하면 N번째 색을 선택하면 안된다.

 

그러므로 K개의 색을 선택하는 경우는 크게 2개로 나눌 수 있다.

 

1. 1번째 색을 선택하고, N번째 색을 선택하지 않은 경우

2. 1번째 색을 선택하지 않으면서 N번째 색을 선택하지 않은 경우

3. 1번째 색을 선택하지 않으면서 N번째 색을 선택한 경우

 

 

여기서 1번과 2번의 경우는 DP[N번째 색을 선택X][ K개 선택 ][N번째 까지 탐색] 에 전부 포함되어 있다.

그러므로 3번의 경우만 계산하면 된다.

 

잘 생각해보면 1번과 3번의 경우의 수는 수가 같을 수 밖에 없다.

 

그러므로 1번째 색을 선택하면서 N번째 색을 선택하지 않은 경우를 구하면  DP[N-1번째 색을 선택][K개 선택][N-1번째 까지 탐색] 의 경우와 같다는 사실을 알 수 있다.

 

최종적으로 위의 경우의 수를 더해 값을 출력하면 정답이 된다.

 

+ 위 부분이 헷갈리면 아래 그림을 참고해 한번 생각해보자

 

 

Code

 

 

#include <iostream>
#include <vector>
using namespace std;
const int mod = 1000000003;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int N, K;
	cin >> N >> K;
	vector<vector<vector<long long>>> DP(2, vector<vector<long long>>(K + 1, vector<long long>(N + 1, 0)));
	DP[0][0][1] = 1; // [선택여부][K개 선택됨][N번째 색]
	DP[1][1][1] = 1;
	for (int i = 2; i < N; i++)
	{
		DP[0][0][i] += DP[0][0][i - 1];
		for (int j = 1; j <= K; j++) {
			DP[0][j][i] += DP[0][j][i - 1] + DP[1][j][i - 1]; //i번째 색을 선택하지 않았다는 뜻
			DP[1][j][i] += DP[0][j - 1][i - 1]; //i번째 색을 선택했다는 뜻
			
			DP[0][j][i] %= mod;
			DP[1][j][i] %= mod;
		}
	}
	DP[0][K][N] += DP[0][K][N - 1] + DP[1][K][N - 1];
	DP[1][K][N] += DP[0][K - 1][N - 1];
	long long Ans = 0;
	Ans += DP[0][K][N] + DP[1][K][N - 1];
	cout << Ans % mod;

	return 0;
}

 

---

3번의 경우가 그림의 경우로 바꿔진다는 사실을 보이는게 생각보다 어려웠다.

머리로는 이해가 되는데 막상 말로 설명하려니 계속해서 헷갈렸다.

실제로 그림을 그려보면 이해가 잘 되는데, 생각으로만 하려니 더 어려웠나보다;;

 

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