[BOJ/백준][Gold4] 1301 : 비즈 공예 (C++)

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

1301번: 비즈 공예

 

 

[난이도] Gold4
[유형] DP

[풀이]
구슬의 종류가 최대 5개밖에 되지 않고, 각각 10개 이하이기 때문에 7차원 DP로 해결할 수 있습니다.
long long dp[7][7][11][11][11][11][11] 배열을 이용하였습니다.
dp[prev][cur][a][b][c][d][f]에서 cur은 이전에 선택한 구슬의 색, prev는 cur 이전에 선택한 구슬의 색이며
a,b,c,d,f는 각각 구슬의 남은 개수입니다.

prev와 cur이 아닌 구슬을 선택하는 경우의 수를 더해주면 됩니다.
모든 구슬을 사용했을 때가 가능한 경우의 수가 되므로 1을 return 해서 정답에 포함될 수 있게 해줍니다.

 

#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
int N,a[6];
ll dp[7][7][11][11][11][11][11];
ll sol(int prev,int cur,int a,int b,int c,int d,int f){
    if(a==0&&b==0&&c==0&&d==0&&f==0) return 1;
    ll& ret=dp[prev][cur][a][b][c][d][f];
    if(ret!=-1) return ret;
    ret=0;
    if(a>0 && prev!=0 && cur!=0) ret+=sol(cur,0,a-1,b,c,d,f);
    if(b>0 && prev!=1 && cur!=1) ret+=sol(cur,1,a,b-1,c,d,f);
    if(c>0 && prev!=2 && cur!=2) ret+=sol(cur,2,a,b,c-1,d,f);
    if(d>0 && prev!=3 && cur!=3) ret+=sol(cur,3,a,b,c,d-1,f);
    if(f>0 && prev!=4 && cur!=4) ret+=sol(cur,4,a,b,c,d,f-1);
    return ret;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    printf("%lld",sol(6,5,a[0],a[1],a[2],a[3],a[4]));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1301.cpp