문제를 간단하게 설명하자면 여러 토막난 막대기들이 있는데 원래 같은 길이의 막대기 몇 개를 여러개로 쪼개서 만든 것이다. 이 때 이 토막난 막대기들을 보고 자르기 전 원래 막대기의 길이를 알아내는 것. (가장 짧은 길이)

예를 들어 입력이 5, 2, 1, 5, 1, 2, 5, 2, 1 과 같이 주어졌을 때
답은 (5,1) (5,1) (2,2,2) 로 6 이 된다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solucion;
int failed;
int lenghtSol;
int *usado;
int *stickSize;

int compara(const void *a, const void *b)
{
 int A,B;

 A = *(int *)a;
 B = *(int *)b;
 return(B-A);
}

int allUsed(int *usado, int N)
{
 int i;

 for(i=0;i<N && usado[i]==1;i++);

 if(i==N) return 1;
 else  return 0;
}

void tryIt(int lenght, int acum, int total, int n)
{
 int k;

 for(k = 0 ; k < n && solucion == 0 ; k++)
 {
  if(usado[k] == 0 && (acum + stickSize[k]) <= lenght)
  {
   usado[k] = 1;
   acum += stickSize[k];
   total -= stickSize[k];
  }
 }
 if(acum == lenght)
 {
  if(total == 0)
  {
   solucion = 1;
   lenghtSol = acum;
  }
  else
  {
   if((total%lenght)==0)
   {
    tryIt(lenght, 0, total, n);
   }
  }
 }
}

int main()
{
 int i,N;
 int minLenght,maxLenght;

 usado = NULL;
 stickSize = NULL;

 while(scanf("%d",&N)==1)
 {
  if(N==0) break;
  solucion = 0;
  minLenght=maxLenght=0;
 
  if(usado!=NULL) free(usado);
  usado = (int *)malloc(sizeof(int)*N);

  if(stickSize!=NULL) free(stickSize);
  stickSize = (int *)malloc(sizeof(int)*N);
 
  for(i=0;i<N;i++) {
   scanf("%d",&stickSize[i]);

   maxLenght += stickSize[i];
   if(stickSize[i] > minLenght)
    minLenght = stickSize[i];
  }
  lenghtSol = maxLenght;

  qsort(stickSize,N,sizeof(int),compara);

  for(i = minLenght + 1 ; i < maxLenght && solucion == 0 ; i++) {
   failed = 0;
   memset(usado, 0, sizeof(int) * N);
   tryIt(i, 0, maxLenght, N);
  }
  printf("%d\n",lenghtSol);
 }

 return 0;
}

문제의 예제에 적용해 보면
입력 : 5, 2, 1, 5, 2, 1, 5, 2, 1

내림차순으로 정렬 - 5, 5, 5, 2, 2, 2, 1, 1, 1
답이 될 수 있는 값은 5 ~ 24 사이에 있으므로 5부터 루프를 돌면서 확인한다.

1. 5 선택             남은 막대 : 5,5,2,2,2,1,1,1       완성 (5)
2. 5 선택             남은 막대 : 5,2,2,2,1,1,1         완성 (5), (5)
3. 5 선택             남은 막대 : 2,2,2,1,1,1            완성 (5), (5), (5)
4. 2 선택             남은 막대 : 2,2,1,1,1              완성 (5), (5), (5)   조합중 (2)
5. 2 선택             남은 막대 : 2,1,1,1                완성 (5), (5), (5)   조합중 (2, 2)
5. 2 선택             남은 막대 : 1,1,1                  완성 (5), (5), (5)   조합중 (2, 2, 2) <- 5를 초과
6. 1 선택             남은 막대 : 2,1,1                  완성 (5), (5), (5) (2, 2,1)
7. 2선택
8. 1선택
9. 1선택    
-----
모두 사용했지만 길이가 5인 조합을 완성할 수 없음 -> 6이 답인지 확인

1. 5 선택             남은 막대 : 5,5,2,2,2,1,1,1       조합중 (5)
2. 5 선택             남은 막대 : 5,2,2,2,1,1,1         조합중 (5,5) <- 6을 초과하므로 선택하지 않음
3. 5 선택             남은 막대 : 5,2,2,2,1,1,1         조합중 (5,5) <- 6을 초과하므로 선택하지 않음
4. 2 선택             남은 막대 : 5,5,2,2,1,1,1         조합중 (5,2) <- 6을 초과하므로 선택하지 않음
5. 2 선택             남은 막대 : 5,5,2,2,1,1,1         조합중 (5,2) <- 6을 초과하므로 선택하지 않음
6. 2 선택             남은 막대 : 5,5,2,2,1,1,1         조합중 (5,2) <- 6을 초과하므로 선택하지 않음
7. 1 선택             남은 막대 : 5,2,2,2,1,1           조합중 (5,1) <- 완성
..
..

.. 1 선택             남은 막대 :           완성 (5,1) (5,1) (5,1), (2,2,2)

-----

모든 막대를 사용하여 6의 조합을 만들었음 -> 답은 6