Difference between r1.2 and the current
@@ -67,6 +67,6 @@
}}}
= 아이디어 =
== 15이원준 ==
= 아이디어 =
== 15이원준 ==
* d[[c1]][[c2]][[c3]][[c4]][[c5]][[p1]][[p2]] : ci는 i번째 보석의 갯수, p2는 이전 보석, p1은 지금보석
* search에서 arr[i] 는 이전전 보석 이전에 i번째 보석의 갯수이고 p1은 이전 보석, p2는 지금 보석
* dp c1 c2 c3 c4 c5 p1 p2 : ci는 i번째 보석의 갯수, p2는 이전 보석, p1은 지금보석
* search에서 arr i 는 이전전 보석 이전에 i번째 보석의 갯수이고 p1은 이전 보석, p2는 지금 보석
* i가 p1, p2와 다르고 i번째 보석이 남아있다면 i번째 보석을 하나 빼고 -> i가 p2바로 전 보석이 되고 p2가 현 보석이 되된다.3.1. 15이원준 ¶
#include<iostream>
#include<cstring>
using namespace std;
long long int dp[12][12][12][12][12][6][6] = {0,};
long long int arr[5] = {0,};
long long int n;
long long int search(long long int now[5], long long int p1, long long int p2){
if(now[0] + now[1] + now[2] + now[3] + now[4] == 0){
return 1;
}
if(dp[now[0]][now[1]][now[2]][now[3]][now[4]][p1][p2] != -1){
return dp[now[0]][now[1]][now[2]][now[3]][now[4]][p1][p2];
}
long long int ans = 0;
for(long long int i = 0; i<n; i++){
if(!now[i]){
continue;
}
if(p1 == i || p2 == i){
continue;
}
now[i]--;
ans += search(now, p2,i);
now[i]++;
}
dp[now[0]][now[1]][now[2]][now[3]][now[4]][p1][p2] = ans;
return ans;
}
int main(){
cin>>n;
for(long long int i = 0; i<n; i++){
scanf("%d", &arr[i]);
}
memset(dp,-1,sizeof(dp));
long long int ans = 0;
for(long long int i = 0; i<n; i++){
for(long long int j = 0; j<n; j++){
if(i == j){
continue;
}
if(!arr[i] || !arr[j]){
continue;
}
arr[i]--;
arr[j]--;
ans += search(arr,i,j);
arr[i]++;
arr[j]++;
}
}
cout << ans<<endl;
}
