[알고리즘문제] 프로그래머스 - N으로 표현

완전탐색으로 모든 경우의 수를 다 구했고 완전탐색을 구현하는데 dfs를 사용했다.

for문에서의 n은 5,55,555,555...5555555까지 숫자가 커진다. 각각의 숫자에 대해 모두 +,-,*,/의 경우를 검사한다. 근데 만약 sum이 0인 경우에 /,*을 하면 의미가 없기 때문에 이 경우는 체크해준다

 

기저조건으로 depth가 9와 같거나 크다면 return을 해준다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int N,number;
int result = 987654321;

void recur(int sum,int depth){
    
    if(depth >= 9){
        return;
    }
    
      if(sum==number){
          result = min(result,depth);
        }
    
    int n = 0;
    for(int i=0;i<8;i++){
        
        n = (n*10)+N;
        
        recur(sum+n,depth+i+1);
        recur(sum-n,depth+i+1);
        
        if(sum!=0){
             recur(sum*n,depth+i+1);
             recur(sum/n,depth+i+1);
        }
    }
}

int solution(int a, int b) {
    
    N = a;
    number = b;
    int answer = 0;
    
    recur(0,0);
    
    if(result > 8){
        return -1;
    }
    return result;
}