타겟 넘버

들어가는 말

주어진 수를 차례대로 더하거나 빼서 target의 숫자를 구할 수 있는 식의 개수를 반환하는 문제다.

깊이 우선 탐색(Dfs)를 쓰면 된다. 깊이 우선 탐색이란 한 방향으로 쭉 내려간 뒤 마지막에 도달하면 그 전의 값으로 돌아가 같은 일을 반복하는 거다. 이는 스택이나 재귀함수로 구현할 수 있다. 때문에 이 문제는 재귀함수를 이용해서 풀 수 있다.

여기서 중요한 점 또 하나. 벡터로 인접 리스트를 구현할 수 있다는 거다.

코드 설명

일단 answer을 전역 변수로 둔다. 그 다음 재귀함수인 dfs를 선언한다. 여기서 만일 idx가 그래프 끝까지 내려갔고 총 합이 target와 같다면 answer을 ++해준다. 그리고 아닐 경우에는 return을 한다. 재귀함수를 두 개 호출하는데, 하나는 더하기를 해주는 왼쪽이고 또 다른 하나는 빼기를 해주는 오른쪽이다.

그리고 solution함수에서 dfs를 호출하면 된다. 이때 변수는 numbers, target, idx(0), current(0)이다. 마지막으로 전역 변수인 answer을 리턴하면 된다.

코드

#include <string>
#include <vector>

using namespace std;
int answer = 0;
/*배열은 인접리스트다*/

void dfs(vector<int> numbers, int target, int idx, int current){
    if(idx == numbers.size()){
        if(current == target){
            answer++;
        }
        return;
    }
    dfs(numbers, target, idx+1, current+numbers[idx]);
    dfs(numbers, target, idx+1, current-numbers[idx]);
}
int solution(vector<int> numbers, int target) {
    
    dfs(numbers, target, 0, 0);
    return answer;
}