public class PossibleOrders
{
int N;
long sum;
long comb(long n, long r) {
long denom=1, numer=1;
while (r > 0) {denom *= n--; numer *= r--;}
return denom / numer;
}
void calcul(long[] cnt, int rem, int min) {
for (int i=min; i<=rem; i++) {
long[] c = new long[N+1];
System.arraycopy(cnt,0,c,0,N+1);
c[i]++;
if (rem-i>0)
calcul(c, rem-i, i);
else if (rem-i==0) {
long r=N,s=1,f=0,d=1;
for (int j=N; j>0 && r>0; j--) {
if(c[j]!=0) {
if(j>1)
for (long tot=r; r-c[j]*j != tot; tot-=j)
s *= comb(tot,j);
r -= c[j]*j;
f += c[j];
if(j>1 && c[j]>1)
for (long k=c[j]; k>1; k--)
d *= k;
if(r==0) {
for(long k=f; k>1; k--)
s *= k;
sum += s/d;
}
}
}
}
}
}
public long howMany(int num, String[] facts) {
N = num; sum=1;
String[] str = new String[facts.length];
// Cartegorizing equal elements
if (facts.length != 0) {
for(int i=0; i < str.length; i++)
str[i] = " ";
for (int i=0; i < facts.length; i++) {
String[] n = facts[i].split("=");
String s1 = " " + n[0] + " ";
String s2 = " " + n[1] + " ";
if(s1.equals(s2)) continue;
for (int j=0; j < str.length; j++) {
if(str[j].contains(s1) && str[j].contains(s2))
break;
else if(!str[j].contains(s1) && !str[j].contains(s2) && str[j].length()!=1)
continue;
if(!str[j].contains(s1)) str[j] += n[0] + " ";
if(!str[j].contains(s2)) str[j] += n[1] + " ";
break;
}
}
for (int i=str.length-1; i > 0; i--) {
if(str[i].length()==1) continue;
LOOP:
for (int j=i-1; j >= 0; j--) {
String[] n = str[i].split(" ");
for (int k=1; k < n.length-1; k++) {
String s1 = " " + n[k] + " ";
if(str[j].contains(s1)) {
for (int l=1; l < n.length-1; l++) {
String s2 = " " + n[l] + " ";
if(!str[j].contains(s2)) str[j] += n[l] + " ";
}
str[i] = " ";
break LOOP;
}
}
}
}
}
// Eliminating empty elements
for (int i=str.length-1; i > 0; i--) {
if(str[i].length() != 1) {
for (int j=i-1; j >= 0; j--) {
if(str[j].length()==1) {
str[j] = str[i];
str[i] = " ";
}
}
if(str[i].length() != 1) break;
}
}
// Subtracting equal elements from N
for (int i=0; i<str.length && str[i].length()!=1; i++)
N -= str[i].split(" ").length-2;
for (int i=1; i <= N/2; i++) {
long[] cnt = new long[N+1];
cnt[i]++;
calcul(cnt,N-i,i);
}
return sum;
}
}
Explanation
동적 프로그래밍 문제이지만 조합과 순열을 사용하여 문제를 다르게 해결했다.
같은 순서(=)인 숫자들은 1개로 처리하고 순열로 돌리면 해결된다. 왜냐하면 같은 숫자이기 때문에 조합을 돌려봤자 의미가 없기 때문이다. (예: 1,1,1,1 을 조합으로 돌리는 경우 항상 1,1,1,1 이 나온다.)
최근 덧글