막대기 퀴즈 오답-_-

지난 번에 올렸던 막대기 퀴즈 정답. 인줄 알았으나 혁민이가 오답임을 밝힘.

문제보기

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

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

누가 작성한건지 모르겠지만 혁민이가 google 에서 찾아와서 정리해준 코드

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

기본적인 원리를 살펴보면 너무 너무 간단하다.
모든 퀴즈가 그렇듯이.. 답을 보면 신기하면서도 허무한 마음 ㅋ 이었으나 답이 아니군 -_-

잘려진 막대 중에서 가장 길이가 긴 것을 찾는다.
잘리기 전의 막대는 이것보다 길기 때문에  이 값에서 시작하여 모든 막대 길이의 합(전체가 하나의 막대로 이루어진 것을 토막낸 경우)까지가 답이 될 수 있는 값이다.
이제 루프를 돌면서 가능한 모든 값들에 대해서 조합이 가능한지를 확인하면 되는데..

1. 사용하지 않은 막대기를 우선 내림차순으로 정렬한다.
2. 사용하지 않은 막대 중에서 가장 긴 막대기를 뽑는다. (정렬된 막대 중에 첫번째 선택)
3. 나머지 막대들과 선택된 막대들을 조합하여 답이라고 예상되는 값을 초과하는지 체크.
4 .초과하지 않을 경우 해당 막대를 선택하고 위 과정을 재귀적으로 반복.

문제의 예제에 적용해 보면
입력 : 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

위의 알고리즘을 어떻게 구현하느냐는 여러 방법이 있겠지만 소스 코드를 보면
막대를 저장하는 배열 하나와 막대의 사용여부를 저장하는 boolean 배열, 이렇게 두 가지를 사용한다.


--------------------
진짜 이문제 풀려구 무지하게 고민했는데 ㅋ

내림차순으로 정렬해서 Greedy choice를 하는 걸로 해서 가장 길이가 긴 막대를 선택하는 방법으로 해서 예상 값을 초과하면 다른 막대를 선택하는 과정을 반복하는 것까지는 생각했는데..

위 소스코드에서처럼 일단 모든 막대를 사용했을 경우에 무조건 답이 아니라고 판단해서는 안된다고 생각했기때문에 (다른 방식으로 조합하면 답이 될 수도 있으므로) 조합의 방법을 바꿔보기 위해서 특정 막대를 선택하기 이전으로 돌아가기 위한 방법이 필요하다.
근데 그걸 어떻게 하면 되지..ㅠ_-  에서 좌절했다.

답이라고 예상하는 값을 초과할 경우 선택하지 않는 방법을 통해서 답이 될 수 없는 조합을 제거하고 재귀적인 호출 방식으로 모든 조합을 확인할 수 있었나보다.. -> 안되잖아 -_-