[프로그래머스/c++] Lv2 타겟 넘버

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

dfs를 사용하는 문제이다. 

 

n개의 정수가 주어지고 각 정수는 +, - 배치에 따라 값이 달라진다. n개의 정수가 주어질 때 경우의 수는 2의 n승이다. 

 

각 값이 +,-에 따라 달라지기 때문에 깊이 우선 탐색을 하면 값을 구할 수 있다. 계속 반복해야되기 때문에 재귀를 사용한다는 것을 안다면 dfs 사용하는 문제라는 것을 빠르게 알 수 있다. 

#include <string>
#include <vector>

using namespace std;

//dfs
void dfs(vector<int> numbers, int target, int& answer, int count = 0, int sum = 0) {
	//dfs 끝까지 왔을 때, answer 출력
    if (count == numbers.size() - 1) {
        if (target == sum + numbers[count])
            answer++;
        if (target == sum - numbers[count])
            answer++;
        return;
    }
    //+, - 둘 다 깊이 우선 탐색 해줌
    dfs(numbers, target, answer, count + 1, sum - numbers[count]);
    dfs(numbers, target, answer, count + 1, sum + numbers[count]);
}

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

    dfs(numbers, target, answer);

    return answer;
}