[프로그래머스] N으로 표현 c++ DFS코드

문제 링크 

 

리뷰 

처음에 감을 못잡은 문제... 어떤 파라미터 넘겨서 탐색해야되지? 다음에 다시 풀어봐야겠다. 

 

맞았습니다 코드 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int global_N, target_number;
int max_cnt = 8;
int min_cnt = 1 + max_cnt;

void dfs(int cur_num, int cnt){ // (현재 숫자, N을 사용한 개수)
  if(cnt > max_cnt) return;
  else if(cur_num == target_number){
    min_cnt = min(cnt, min_cnt);
    return;
  }

  int n = 0;  // 계산할 숫자 n 
  for(int i = 1; i <= 6; i++){ // N을 1개~6개 사용가능
    // 계산할 숫자 n -> N, NN, NNN
    n = n*10 + global_N;
      
    dfs(cur_num + n, cnt + i);
    dfs(cur_num - n, cnt + i);
    if(cur_num != 0 || cnt > 8){
      dfs(cur_num * n, cnt + i);
      dfs(cur_num / n, cnt + i);
    }
  }
}

int solution(int N, int number) {
  global_N = N;
  target_number = number;
  dfs(0, 0);
  return (min_cnt == 9) ? -1 : min_cnt;
}