[프로그래머스] level 3 - N으로 표현, C++

https://programmers.co.kr/learn/courses/30/lessons/42895

프로그래머스

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성해라.

#include <string>
#include <vector>
 
using namespace std;
 
// 8보다 큰 경우는 -1을 return 해야하므로 초기값을 9로 한다.
int answer = 9;
 
void cal(int n, int goal, int cnt, int sum) {
    // 8보다 큰 경우
    if (cnt > 8) return;
    
    // 목표값
    if (sum == goal) {
        if (answer > cnt) answer = cnt;
    }
    
    int tmp = 0;
    for (int i = 1; i <= 8; i++) {
        // n을 추가
        tmp = (tmp*10) + n;
        
        // 사칙연산
        cal(n, goal, cnt+i, sum + tmp);
        cal(n, goal, cnt+i, sum - tmp);
        cal(n, goal, cnt+i, sum / tmp);
        cal(n, goal, cnt+i, sum * tmp);
    }
}
 
int solution(int N, int number) {
    cal(N, number, 0, 0);
    if (answer > 8) answer = -1;
    return answer;
}