[Programmers 43165] 타겟넘버

문제 출처

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

처음에 어떻게 풀어야 하는지 고민하던 문제다. 전체 numbers를 root로 두고 depth를 1씩 늘려가는 트리형식으로 내려가는 형식으로 풀이했다. 

[1, 1, 1, 1, 1]이 있다면 

첫번째 depth는 1과 -1이 될 것이고 두번째는 1에서 파생된 1+1, 1-1 // -1에서 파생된 -1+1, -1-1 두가지가 될 것이다. 이로 쭉쭉 내려가서 numbers.size()가 5이므로 depth는 5까지 뻗어나갈 수 있는데 이때 target과 현재 depth에서의 합계가 같으면 전역변수 ret을 +1해 준후 return해준다.

소스

#include <string>
#include <vector>
 
using namespace std;
int ret;
 
void dfs(vector<int> &numbers, int target, int sum, int depth) {
    if(depth >= numbers.size()) {
        if(sum==target)
            ret++;
        return;
    }
    dfs(numbers, target, sum+numbers[depth], depth+1);
    dfs(numbers, target, sum-numbers[depth], depth+1);
}
 
int solution(vector<int> numbers, int target) {
    dfs(numbers, target, numbers[0] , 1);
    dfs(numbers, target, numbers[0]*-1, 1);
 
    return ret;
}