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

 

고민하다가 모르겠어서 풀이를 보고 생각을 해 보았습니다..

DFS에 대한 완벽한 이해가 안되었던 것 같고, 뭔가 재귀인 것 같다고 생각하긴 했지만 구현 방식이 생각나지 않았다.
재귀.. 너무 어려워요

sum과 index를 기록해가며 DFS를 진행한다.

제일 먼저 sum = 0, index = 0을 매개변수로 DFS 함수를 호출하면 DFS 함수 내에서 더하기 연산(sum = sum+numbers[0], index = 1), 빼기 연산 (sum = sum-numbers[0], index = 1)을 순차적으로 진행한다. sum은 numbers의 각 원소에 맞게 더하거나 빼게 되고, index는 다음 numbers의 원소로 넘어갈 때마다 1씩 증가한다.

종료 조건은 index와 numbers의 길이가 같은 경우이다. 이때 sum과 target이 같으면 answer에 1을 더해준다. 
재귀니까 종료 조건을 1번으로 생각하자!

왜! DFS를 썼냐고 하면,,!
numbers의 첫 원소부터 마지막 원소까지 더하는 경우와 빼는 경우를 생각하며 순서대로 한 번 씩 계산을 진행해야하기 때문에 DFS를 쓴다.
트리 형식을 생각하면 좀 더 이해하기 쉬운 것 같다. 위에서 아래로 쭉 내려가면서 재귀적으로 연산을 한다. 

DFS를 이럴때 쓰는구나~ 싶었다..

#include <string>
#include <vector>

using namespace std;
int answer =0;
void dfs(vector<int> numbers, int target, int sum, int index){
    // 종료 조건
    // index와 numbers의 크기가 같은 경우 dfs 끝. 
    // 이때마다 sum과 target이 같은지 계산해서 같으면 answer++
    if(index == numbers.size()){
        if(sum == target)
            answer++;
        return;
    }
    dfs(numbers, target, sum+numbers[index],index+1);//numbers 베열의 다음 원소를 +
    dfs(numbers, target, sum-numbers[index],index+1);//numbers 베열의 다음 원소를 -
}

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

}