[낙 곡] P1120 작은 나무 막대기 [데이터 강화 판]

//  P1120    
#include
#include
#include
int n,cnt,sum,maxx,t,m;
int a[100],p[110];
bool b[100];
using namespace std;
int cmp(const int&a,const int&b) {
    return a>b;
}
void dfs(int l,int s,int last) {
    if(s==m) {//         
        s=0;//     
        l++;//           +1
        last=1;//            
    }
    if(l==t-1) {//   3   
        printf("%d
",m);exit(0);
    }
    for(int i=last; i<=cnt; i++) {//   4   
        if(s+a[i]>m||b[i]) continue;//         [  5]
        if(a[i]==a[i-1]&&!b[i-1]) continue;//   6   
        if(s+p[i]return;//   7   [   ！]
        b[i]=1;
        dfs(l,s+a[i],i+1);
        b[i]=0;//         
        if(s==0)return;//   8   
        if(s+a[i]==m)return;//   9   
    }
}
void init() {
    int x;
    for(int i=1; i<=n; i++) {
        scanf("%d",&x);
        if(x<=50) {
            a[++cnt]=x;//    
            sum+=x;//  
            maxx=max(maxx,x);//     
        }
    }
}
int main() {
    int i,j,k;
    scanf("%d",&n);
    init();//  ，         50   ！
    sort(a+1,a+n+1,cmp);// 1   
    for(i=n;i>=1;i--)
        p[i]=p[i+1]+a[i];//       ，    
    for(i=maxx; i<=sum/2; i++) {// 2   
        if(sum%i==0) {//              ，      
            t=sum/i;//            
            m=i;//         
            dfs(0,0,0);//  
        }
    }
    printf("%d
",sum);//              ，       ，    
    return 0;
}