Programers N으로 표현

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

코딩테스트 연습 - N으로 표현

프로그래머스 N으로 표현 문제입니다.  이전 타켓넘버 문제와 비슷합니다.

#include <string>
#include <vector>
#define MAX 9

using namespace std;

int minDepth = MAX;
int tartget;
int source;

int  min(int a, int b) {
	return a > b ? b : a;
}

void dfs(int depth, int num) {
	if (depth >= MAX) {
		return;
	}

	if (num == tartget) {
		minDepth = min(depth, minDepth);
	}

	int operand = 0;
	for (int i = 1; i <= MAX; i++) {
		operand = operand * 10 + source;

		dfs(depth + i, num + operand);
		dfs(depth + i, num - operand);

		if (num != 0) {
			dfs(depth + i, num * operand);
			dfs(depth + i, num / operand);
		}
	}
}

int solution(int N, int number) {
	int answer = 0;
	tartget = number;
	source = N;
	dfs(0, 0);
	answer = ((minDepth >= MAX) ? -1 : minDepth);

	return answer;
}

아이디어

결국에는 완전탐색을 해야하는데 3 33 333같은 숫자에 대한 처리와 완전탐색의 방법 구현으로 판단하여 DFS 사용