※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
이 문제는 DP 중에서도 상태 DP라는 유형으로 풀 수 있는 문제입니다. 사실 상태 DP라는 표현이 공식적으로 있는지는 모르겠지만.. 상태 DP의 뜻은 말 그대로 현재 남아있는 상태, 개수 등을 그대로 기록하여 메모이제이션을 한다는 의미입니다. 상태를 그대로 저장하기 때문에 이러한 유형의 문제를 풀 때는 bitmask 또는 다차원 배열을 사용하게 됩니다.
색의 최대 개수는 5개, 그리고 구슬의 개수는 10개를 넘지 않는다고 하였고, 연속된 3개의 칸에 같은 색이 두 번 올 수 없으므로 색의 정보는 2가지를 저장해야 합니다. 따라서 이를 상태 DP로 저장하기 위한 배열로 변환하면 무려 7차원의 배열이 생성됩니다. 이를 배열로 정리하면 $dp[b1][b2][b3][b4][b5][c1][c2]$ 가 됩니다.
그 다음 맨 앞 구슬 2개를 끼울 수 있는 경우를 모두 찾아 2개를 끼워준 뒤, 직접 재귀함수를 돌며 가능한 모든 경우를 탐색해 줍니다. 상태를 메모이제이션 하기 때문에 전체 탐색횟수는 상당히 줄어들게 됩니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
int n;
ll ans, cmp, v[5], dp[11][11][11][11][11][5][5];
ll dfs(ll c1, ll c2)
{
ll &ret = dp[v[0]][v[1]][v[2]][v[3]][v[4]][c1][c2];
if (ret != -1) return ret;
if(!cmp) return ret=1;
ret = 0;
for (int i = 0; i < n; i++)
{
if (i == c1 || i == c2 || !v[i]) continue;
v[i]--, cmp--;
ret += dfs(c2, i);
v[i]++, cmp++;
}
return ret;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> v[i], cmp += v[i];
memset(dp, -1, sizeof(dp));
for (int i = 0; i<n; i++)
for (int j = 0; j < n; j++)
{
if (i == j || !v[i] || !v[j]) continue;
v[i]--, v[j]--, cmp -= 2;
ans += dfs(i, j);
v[i]++, v[j]++, cmp += 2;
}
cout << ans;
}