[알고리즘 8.1.4] 재귀함수 - dessert

문제

---

농부 존은 소들의 저녁식사 줄 세우는 새로운 방법을 개발 했다. N(1~15)마리의 소들을 순서대로 세 워놓은 후, 각 소들 사이에 +, - , . 셋 중 1가지가 써져있는 냅킨을 배치해서 최종 결과가 0 이 되게 해야 하는 것이다. 점(.)이 써져있는 냅킨을 통해 더 큰 수를 만들 수 있게 된다. 아래와 같은 경우를 보자. (ps .이 써져있는 냅킨은 '공백'이라고 생각하면 된다.) 1-2.3-4.5+6.7 이와 같은 배치는 1-23-45+67 을 나타낸다. 결과는 0 이다. 10.11은 1011 로 해석된다.

 

입력

---

첫 째 줄에는 소들의 수 N(1 ≤ N ≤ 15)이 입력된다.

 

출력

---

처음 20줄에 대해 가능한 20가지 답을 출력하는데, 사전 순으로 앞선 것을 출력한다. 순서는 +가 가장 앞서고 -와 . 이 순서대로 뒤따른다. 답이 20개 이하라면 가능한 답을 각 숫자와 문자 사이에 공백을 두고 출력한다. 모두 출력한다. 20개를 초과하는 경우 21번째 답부터는 출력하지 않는다. 마지막 줄에는 가능한 답의 총 가지수를 출력한다.

 

예제 입력

7

예제 출력

1 + 2 - 3 + 4 - 5 - 6 + 7

1 + 2 - 3 - 4 + 5 + 6 - 7

1 - 2 + 3 + 4 - 5 + 6 - 7

1 - 2 - 3 - 4 - 5 + 6 + 7

1 - 2 . 3 + 4 + 5 + 6 + 7

1 - 2 . 3 - 4 . 5 + 6 . 7

6

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
#include <stdio.h>
 
int totalCount = 0;
 
//현재위치, n값, 현재까지 Sum값, 부호를 저장할 배열, 단순 숫자 배열, 단순 부호 배열.
void dessert(int x, int n, int sum, int temp[], int arr[], int ine[]){
  
  //기저조건
  if(x==n){
    
    //총 합
    int result = arr[0];
    // . 이 연속되었는지 갯수를 세어주는 Count
    int count = 0;
    int countSum = 0;
    int countTemp = 1;
    
    for(int i=0; i<n; i++){
      //
      //printf("%d ",arr[i]);
      //printf("%c ",temp[i]);
      //
      
      if(i==0 && temp[i]==46){
        result -= 1;
      }
      
      if(temp[i-1]==46 && temp[i] !=46){
        result += countSum;
        count = 0;
        countSum = 0;
      }
      
      if(temp[i]==43 && temp[i+1]!=46){
        result += arr[i+1];
        
      }else if(temp[i]==45 && temp[i+1]!=46){
        result -= arr[i+1];
        
      }else if(temp[i]==46){
        
        if(count == 0){
          if(i!=0 && temp[i-1]==43){
            countTemp = 1;
          }else if(temp[i-1]==45){
            countTemp = -1;
          }
          if(arr[i]>=9){
            countSum = (arr[i]*100 + arr[i+1])*countTemp;
          }else{
            countSum = (arr[i]*10 + arr[i+1])*countTemp;
          }
          count++;
          
        }else{
          if(arr[i]>=9){
            countSum = countSum * 100 + (arr[i+1]*countTemp);
          }else{
            countSum = countSum * 10 + (arr[i+1]*countTemp);
          }
          
          count++;
        }
        
        if(i==n-1){
          result += countSum;
        }
        
        if(count==n){
          result -= 1;
        }
        
      }
    }
    //
    //printf("%d",arr[n]);
    //printf("  =  %d",result);
    //printf("\n");
    //
    
    
    // ------------------------------------------------------------------
    // 20가지 답을 출력하는 문제가 이해가 안됌...
    // ------------------------------------------------------------------
    if(result == 0){
      if(totalCount<20){
        for(int i=0; i<n; i++){
          printf("%d ",arr[i]);
          printf("%c ",temp[i]);
        }
       printf("%d\n",arr[n]);
      }
      totalCount++;
    }
    
    return;
    
  }else{
    
    for(int i=0; i<3; i++){
      temp[x] = ine[i];
      dessert(x+1, n, 0, temp, arr, ine);
    }
    return;
    
  }
  
}
 
int main() {
  
  //입력 크기 초기화
  int n;
  scanf("%d",&n);
  
  //현재까지의 값
  int sum = 0;
  
  //입력 란에 따른 숫자 배열 초기화
  int arr[25];
  int temp[25];
  
  for(int i=0; i<n; i++){
    arr[i] = i+1;
  }
  
  //부호 배열 초기화
  int ine[3];
  ine[0] = '+';
  ine[1] = '-';
  ine[2] = '.';
  
  dessert(0, n-1, 0, temp, arr, ine);
  
  //if(totalCount<20){
  //  printf("%d",totalCount);
  //}
  printf("%d",totalCount);
 
  
  return 0;
}