[프로그래머스] 타겟 넘버 (깊이/너비 우선 탐색 DFS/BFS)

프로그래머스 타겟 넘버 문제

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43165

출처 프로그래머스

풀이 과정 생각

1. 배열 numbers의 값들을 더하고 뺀 모든 결과를 찾는다.

2. 최종 결과 값 중에서 target의 값과 일치한 경우의 수들을 합친다.

 

모든 배열 numbers의 값을 더하기 위해 sum 인자 생성

마지막 배열에 도달 했는지 확인하기 위해 count 인자 생성

dfs로 각각의 위치한 결과를 합치기 위해 answer을 &로 접근하여 저장

 

풀이 코드

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


void dfs(vector<int> numbers, int target, int sum, int count, int& answer)
{
	if (count == numbers.size())
	{
		if (target == sum)
			answer++;
		return;
	}
	dfs(numbers, target, sum + numbers[count], count + 1, answer);
	dfs(numbers, target, sum - numbers[count], count + 1, answer);
}
int solution(vector<int> numbers, int target)
{
	int answer = 0;
	int count = 0;
	dfs(numbers, target, 0, 0, answer);
	return answer;
}


int main()
{
	vector<int> v(5, 1);
	
	cout << solution(v, 3);
}