문제 설명
색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다.
색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다. 시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다.
주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보자. 먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 있게 10개의 색을 선택하는 경우의 수는 2이지만, 시각적 대비 효과를 얻을 수 있게 11개 이상의 색을 선택할 수 없으므로 이 경우의 수는 0이다.
주어진 정수 N과 K에 대하여, N개의 색으로 구성되어 있는 색상환 (N색상환)에서 어떤 인접한 두 색도 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 프로그램을 작성하시오.
제한 사항
풀이
문제를 요약하면, 주어진 N개의 색 중 인접한 색을 고르지 않고 K개를 뽑을 수 있는 경우의 수를 구하면 된다.
처음에는 BFS를 통해 뽑을 수 있는 조합을 만들려고 했지만, 메모리 초과에 걸렸다.
즉, 다른 방법을 찾아야 했다.
바로 DP를 사용한 방법이다.
점화식을 세우는 것은 간단하다.
임의 색에 대해 가능한 경우의 수는 두 가지이다.
- 해당 색을 뽑을 경우
- 해당 색을 뽑지 않을 경우
우선, 해당 색을 뽑을 경우를 생각해보자.
해당 색을 뽑았다면 바로 이전의 색은 뽑지 못한다.
그렇다면 해당 색을 뽑지 않았을 때는 바로 이전색을 뽑아도 된다.
이를 식으로 나타내면 다음과 같다.
dp[i][j] = dp[i-2][j-1] + dp[i-1][j]
한 가지 주의할 점은 정답은 사실 DP[N][K]가 되어야 한다.
하지만, 저렇게 답을 정하면 N번째 색과 1번째 색이 인접한 경우가 포함이 된다.
따라서, 예외처리를 하여 다음과 같은 식이 정답이 된다.
//N번째 색을 선택한 경우 + N번째 색을 선택하지 않은 경우
dp[N-3][K-1] + dp[N-1][K]N번째 수를 뽑았다면 바로 이전의 수와 1번째 수를 뽑지 못한다.
즉, 2~N-1개의 칸을 K-1개로 칠하는 것과 같다.
따라서, dp[N-3][K-1]의 값을 가져와 더하는 것이다.
N번째 수를 뽑지 않았다면, 이전의 값인 dp[N-1][K]개가 된다.
전체 코드
#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;
int N, K;
const int DIV = 1'000'000'003;
int ans = 0;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> K;
vector<vector<int>> dp(N+1, vector<int>(K+1, 0));
for (int i = 0; i < N; ++i)
{
dp[i][0] = 1;
dp[i][1] = i;
}
for (int i = 2; i <= N; i++)
{
for (int j = 2; j <= K; j++)
{
dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % DIV;
}
}
cout << (dp[N - 3][K - 1] + dp[N - 1][K]) % DIV << '\n';
return 0;
}
