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

●문제

 

●입출력

 

문제해석 : numbers에 있는 숫자들로 더하거나 빼서 target숫자를 만들수있는 경우의수를 return

푼방법 : dfs 재귀함수를 사용하여 ind 현재 처리중인 숫자 인덱스와 dfsSum 누적 합을 매개변수로 가지고 계산

주의할점 : 문제에서 주어진 numbers는 vector이니 그냥 값을 dfs에서 복사하면 너무 많이 복사하니

vector<int>numbers는 &참조로 가져오고 int같은 작은 변수값은 그대로 복사해도 무방

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int answer = 0;
//ind -> 몇번째 숫자를 처리중인가 , dfsSum -> 누적 합
void DFS(int ind, vector<int>& numbers, int target, int dfsSum)
{
	//재귀함수 멈추는 조건 ( numbers의 모든 원소를 다 썻을때 )
	if (ind == numbers.size())
	{
		if (dfsSum == target) answer++;
		return;
	}

	DFS(ind + 1, numbers, target, dfsSum + numbers[ind]);
	DFS(ind + 1, numbers, target, dfsSum - numbers[ind]);
}
int solution(vector<int> numbers, int target)
{
	DFS(0, numbers, target, 0);
	return answer;
}


int main(void)
{
	vector<int> numbers = { 1, 1, 1, 1, 1 };
	int target = 3;
	int result = solution(numbers, target);
	cout << result << " ";
}

 

레벨 : 2 

점수 : 1