1R/2016 10 13

오늘의 문제

• 공예

참가자

• 15이원준

코드

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;
}

아이디어

15이원준

• 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가 현 보석이 되된다.