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

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

dfs를 활용해서 풀었습니다. 빼기도 하고 더하기도 하고 이렇게 모든 경우를 다 하기 위해 재귀함수를 사용합니다.

 

#include <string>
#include <vector>

using namespace std;
int ans;

void dfs(vector<int> &numbers, int target, int i, int sum){
    if(i == numbers.size() -1 ){
        if(sum == target)
            ans++;
        return;
    }
    dfs(numbers, target, i+1, sum + numbers[i+1]);
    dfs(numbers, target, i+1, sum - numbers[i+1]);
}

int solution(vector<int> numbers, int target) {
    dfs(numbers, target, 0, numbers[0]);
    dfs(numbers, target, 0, -numbers[0]);
    return ans;
}

 

이 코드는 가지치기로 모든 경우를 탐색한다고 생각하면 이해하기 쉽습니다.

 

타겟넘버 코드의 재귀함수 사용 구조