[Programmers] Lv2. 타겟 넘버 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

DFS로 풀 수 있습니다. 깊이를 numbers의 크기만큼 내려 갔을 때, 이 때까지의 연산 결과와 target이 같으면 answer++ 해주면 됩니다. 더하는 경우와 빼는 경우 두 가지만 있으므로 2개만 재귀로 작성하면 되겠네요.

 

✏️소스 코드 및 결과

#include <vector>
using namespace std;

void DFS(const vector<int>& numbers, const int& target, int sum, int idx, int& answer) {
    if (idx == numbers.size()) {
        if (sum == target)
            answer++;
        return;
    }

    DFS(numbers, target, sum + numbers[idx], idx + 1, answer);
    DFS(numbers, target, sum - numbers[idx], idx + 1, answer);
}

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