타겟넘버 (프로그래머스)

BFS/DFS 문제로 분류되었었는데 처음에는 잘 몰랐다.

 

이미 입력된 값에 +, -를 하는 문제이다. 

 

처음에 +와 - 두가지 경우가 있다. 그리고 +를 선택하면 두번째에 +와 - 두가지 경우가 올 수 있다. 이것이 마지막 번째까지 반복된다. 

 

즉, 배치 가능한 모든 +, -의 경우의 수를 찾는다. 이런 이유로 BFS/DFS 문제로 분류되었다고 생각한다.

 

그림으로 표현하면 다음과 같다.

 

+, -를 해주는 작업은 재귀함수를 사용해주면 된다. 

 

재귀함수로 처음부터 끝까지 +또는 -를 해주는 방향으로 나아가다, 끝까지 도달했을때 target 값과 같은지 확인하고 같다면 answer값을 1 증가시켜주면 된다.

 

코드는 다음과 같다.

#include <vector>
using namespace std;

void search(const vector<int>& info, int idx, int sum, int target, int& result)
{
	// 끝에 도달했을때
	if (idx >= info.size())
	{
		// target과 같다면 정답이므로 1증가
		if (target == sum) ++result;
		return;
	}

	// -를 해주는 경우의 루트
	search(info, idx + 1, sum - info[idx], target, result);
	// +를 해주는 경우의 루트
	search(info, idx + 1, sum + info[idx], target, result);
}

int solution(vector<int> numbers, int target) {
	int answer = 0;
	search(numbers, 0, 0, target, answer);
	return answer;
}