비즈 공예


작성일 : 2017-02-03 21:01:36
조회수 : 413



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


이 문제는 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;
}

비즈 공예 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글