[알고리즘문제] 프로그래머스 - 타겟 넘버

예전에 똑같은 문제를 풀었었는데, dfs로 나올 수 있는 연산자의 경우를 모두 구한 다음 숫자를 하나씩 넣어서 구하는 약간 무식한 방법(?)을 사용했습니다. 그때 방법이 너무 비효율적이라 생각해서 다른 분들의 풀이법을 보고 공부를 했습니다.

 

예전에 제가 풀었던 방법은 ++++, +++-, ++-+...이런식으로 dfs로 모든 경우의 수를 구했고 이 값을 사용하여 number의 인덱스 하나씩 비교해서 값을 더했었습니다. 이런 방법보다는 재귀를 돌리면서 연산이 적용된 현재의 값을 저장하는 방법이 더 직관적이고 괜찮은 방법인 것 같습니다. 

#include <string>
#include <vector>

using namespace std;
vector<int> v;
int t;
int count = 0;

void dfs(int sum,int depth){
    if(depth == v.size()){
        if(sum == t){
            count++;
        }
        return;
    }
    
    dfs(sum+v[depth],depth+1);
    dfs(sum-v[depth],depth+1);
}

int solution(vector<int> numbers, int target) {
    
    v = numbers;
    t = target;
    
    dfs(v[0],1);
    dfs(-v[0],1);
    
    return count;
}