[Level 1][C++] N으로 표현

#include <string>
#include <vector>
#include <cmath>

using namespace std;

int solution(int N, int number) {

     vector<vector<int>> arr(8);  //vector<int> 한 줄당 1개의 N을 씀. N을 쓸 수 있는 건 최대 8번
     if (N == number) 
          return 1;
     else
          arr[0].push_back(N); //맨 첫번째 줄에 N을 집어넣음.

     int i = 1; //N 2개 사용 부터 계산
     while (i < 8)
     {
          int num = arr[i - 1][0] + N * pow(10, i); //arr[i][0]에는 N이 5라면, 5, 55, 555가 저장됨.
          if (num == number)
               return i + 1;  //목표한 값이 맞다면 N사용한 횟수 반환
          else
               arr[i].push_back(num);  

          for (int k = 0; k < (i + 1) / 2; k++) 
          {
               for (int l = 0; l < arr[i - 1 - k].size(); l++)
               {
                    for (int j = 0; j < arr[k].size(); j++)
                    {
                         //덧셈과 뺄셈을 계산하여 정답이 아니면 저장한다. 
                         if (arr[i - 1 - k][l] + arr[k][j] == number || arr[i - 1-k][l] - arr[k][j] == number)
                              return i + 1;
                         else
                         {
                              arr[i].push_back(arr[i - 1 - k][l] + arr[k][j]);
                              arr[i].push_back(arr[i - 1 - k][l] - arr[k][j]);
                         }

                         //곱셈이나 나눗셈 대상이 0이면, 연산의 의미가 없으므로 거른다.
                         if (arr[i - 1 - k][l] == 0 || arr[k][j] == 0)
                              continue;
                         else
                         {
                              //곱셈과 나눗셈을 계산하여 정답이 아니면 저장한다. 
                              if (arr[i - 1 - k][l] * arr[k][j] == number)
                                   return i + 1;
                              else
                                   arr[i].push_back(arr[i - 1 - k][l] * arr[k][j]);

                              if (arr[i - 1 - k][l] % arr[k][j] == 0)
                              {
                                   if (arr[i - 1 - k][l] / arr[k][j] == number)
                                        return i + 1;
                                   else
                                        arr[i].push_back(arr[i - 1 - k][l] / arr[k][j]);
                              }
                         }
                    }
               }
          }
          i++;
     }
     return -1;
}

 

풀고나서 다른 사람들의 풀이를 보니 재귀함수를 정의해서 푸시는 분들이 많았다.
내 방식은 N을 최소 5번 써야 답이 나온다면, N을 1번만 쓴 답과 4번만 쓴  답을 계산 시킨다. 

또 2번만 쓰고 3번만 쓴 답을 계산시킨다. 예를 들면 N이 5이고 목표로 하는 값(number)가 126이라면 5*5*5 +5/5로 5를 5번 사용하는 게 최솟값이다.
N을 2번만 쓴 배열 arr[1] 내에 5/5값이 저장되어 있을 것이고, N을 3번만 쓴 배열 arr[2] 내에 5*5*5값이 저장되어 있을 것이다.
arr[1]과  arr[2]를 서로 계산시킴으로써 언젠간 126을 찾아내서, 5를 최소한으로 사용한 횟수가 5번이란 것을 밝혀낼 것이다.
N을 최소 4번 써야 된다면 N을 1번만 쓴 답과 3번만 쓴  답을 계산 시키고, N을 2번만 쓴 애들끼리 계산 시켜서 답이 나오게 된다.