[DFS] 프로그래머스 N으로 표현 C++

 

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

#include <string>

using namespace std;

int n, num, answer;

void dfs(int depth, int val) {
    if (val == num) {
        answer = min(answer, depth);
        return;
    }
    if (depth >= 8) return;
    
    int temp = 0;
    for(int i=0; i<(8-depth); i++) {
        temp = temp * 10 + n;
        dfs(depth + 1 + i, val + temp);
        dfs(depth + 1 + i, val - temp);
        dfs(depth + 1 + i, val * temp);
        dfs(depth + 1 + i, val / temp);
    }
}

int solution(int N, int number) {
    n = N;
    num = number;
    answer = 9;
    
    dfs(0, 0);
    return (answer > 8)? -1 : answer;
}