[ boj : 1301 ] 비즈 공예

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

1301번: 비즈 공예

해설 : 사실 이런 문제를 보면 dp를 사용해야되는 건 알겠는데 점화식을 세우기가 바로 보이지는 않더라구요....그래서 항상 우리는 조건을 잘 보도록 합시다.

N이 비정상적으로 범위가 작고 구슬의 총 개수도 35를 넘지는 않죠?

처음에는 브루트포스로 해도 되겠다 싶었는데 2^35은 감당이 안될 것 같아 패스했습니다.

점화식을 어떻게 세우면 좋을까요?

목걸이가 완성될 수 있는 조건을 확인하려면 '전전 구슬' 과 '전 구슬' 이 현재 구슬과 색이 전부 다르면 되니깐 변수 2개를 사용해서 표현해 줄 수 있겠죠? 그리고 N의 최대값은 5이니 구슬의 종류는 아무리 많아봐야 5를 넘지 않습니다. 그러면 이 또한 변수 5개로 표현해 줄 수 있습니다.

dp[pprev][prev][x][y][z][p][q] = 전전 구슬과 전구슬이 pprev와 prev 색이고 각 구슬이 x,y,z,p,q 개 남았을때 목걸이를 만들 수 있는 경우의 수

항상 오버플로 조심!

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int n;
ll arr[5], dp[6][6][11][11][11][11][11];

void solve();
ll f(int pprev, int prev, int x, int y, int z, int p, int q);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1;
	while (t--)solve();
	return 0;
}
void solve()
{
	cin >> n;
	for (int i = 0; i < n; i++)cin >> arr[i];
	memset(dp, -1, sizeof(dp));
	cout << f(0, 0, arr[0], arr[1], arr[2], arr[3], arr[4]);
}
ll f(int pprev, int prev, int x, int y, int z, int p, int q)
{
	if (((pprev!=0 && prev!=0) && pprev == prev) || (x < 0 || y < 0 && z < 0 || p < 0 || q < 0)) return 0;
	if (x == 0 && y == 0 && z == 0 && p == 0 && q == 0)return 1;

	ll& ret = dp[pprev][prev][x][y][z][p][q];
	if (ret != -1)return ret;
	ret = 0;

	if (x > 0 && pprev!=1) {
		ret += f(prev, 1, x - 1, y, z, p, q);
	}
	if (y > 0 && pprev!=2) {
		ret += f(prev, 2, x, y - 1, z, p, q);
	}
	if (z > 0 && pprev!=3) {
		ret += f(prev, 3, x, y, z - 1, p, q);
	}
	if (p > 0 && pprev!=4) {
		ret += f(prev, 4, x, y, z, p - 1, q);
	}
	if (q > 0 && pprev!=5) {
		ret += f(prev, 5, x, y, z, p, q - 1);
	}
	return ret;
}