비즈 공예 C++ - 백준 1301

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

문제 접근

처음에는 단순하게 보고 백트래킹을 돌렸지만 TLE.

다른 방법이 필요해 dp로 접근해보았으나,

구슬의 개수를 모든 경우마다 카운트 정렬을 사용하는 것이 불가능했다.

따라서 다른 방법을 써야 했다.

구슬의 종류 수가 최대 5, 구슬의 최대 개수가 35개이므로 모든 경우를 고려해

약 $11^5$ 언저리 값을 구할 수 있다는 사실을 알 수 있다.

그런데 연속된 세 구슬은 같은 색이 아니어야 하기에

앞 두 개를 판별하는 경우의 수까지하면 약 $2.5\cdot 11^6$정도로 볼 수 있고

메모리 초과를 피할 수 있다.

모든 경우를 세는 방법

말 그대로 모든 구슬의 사용 조합 배열을 만든다.

거기다가 2차원을 추가해서 앞 두개의 색상을 알 수 있는 배열을 만든다.

이를 구현하면 $arr[11][11][11][11][11][5][5]$

이와 같이 7차원의 배열이 나온다.

점화식은 다음과 같이 세울 수 있다.

$a,b,c,d,e$를 색상 별 구슬의 사용 횟수라고 하고,

사용된 색상 $i,j$라고 할 때,

$a$구슬에 대한 경우를 구한다고 했을때,

$DP(a,b,c,d,e,i,j)=\sum DP(a-1,b,c,d,e,!i,!j)$ ($i,j$가 안들어가 있는 경우를 의미함)

이를 코드로 구현할 때,

백트래킹과 유사하게 욕심쟁이 판다, 내리막길과 유사하게 구현했다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll dp[11][11][11][11][11][6][6],ans=0;
vector<int> cnt(6,0);
int n,sum=0;

ll solve(int c, int a, int b){
    if(c==0) return 1;
    if(dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][a][b]!=-1) return dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][a][b];
    ll k=0;
    for(int i=1;i<=n;i++){
        if(cnt[i]>0 && a!=i && b!=i){
            cnt[i]--;
            k+=solve(c-1,b,i);
            cnt[i]++;
        }
    }
    return dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]][a][b]=k;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    memset(dp,-1,sizeof(dp));
    cin >> n;
    for(int i=1;i<=n;i++){cin >> cnt[i];sum+=cnt[i];}
    cout << solve(sum,0,0);
    return 0;
}