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

문제 

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

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

 

풀이

- dfs를 이용해서 9번 넘게 N을 사용하면 리턴한다.

- 다음 선택지로 선택할 수 있는 경우의 수는 이전 숫자에 사칙연산을 하는 경우뿐이다.

#include<vector>
#include<algorithm>

using namespace std;

int answer = 9;

void dfs(int N, int number, int count, int currentNumber) {
	if (count >= 9) return;
	if (currentNumber == number) {
		answer = min(answer, count);
		return;
	}
	int temp = 0;
	for (int i = 0; i < 9; i++) {
		temp = temp * 10 + N; //5, 55, 555,...
		dfs(N, number, count + 1 + i, currentNumber + temp);
		dfs(N, number, count + 1 + i, currentNumber - temp);
		dfs(N, number, count + 1 + i, currentNumber * temp);
		dfs(N, number, count + 1 + i, currentNumber / temp);

	}
}

int solution(int N, int number) {
	dfs(N, number, 0, 0);
	if (answer == 9) return -1;
	return answer;
}