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

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

 

 

문제 : 

 

 

 

예시 : 

 

 

 

해결 : 

배열에 주어진 수들에 + 또는 -부호를 붙이고, 그 합을 구하는 문제이다. 

처음에는 배열의 순서까지 고려해야되나 싶었는데, 덧셈과 뺄셈 문제이기 때문에 순서는 고려하지 않아도 된다.

깊이우선탐색(DFS)를 이용하여 문제를 풀었다. 

고려하고 있는 인덱스의 숫자를 더하는 경우와 빼는 경우로 나누고, 이를 각각 재귀함수로 호출하였다. 인덱스가 numbers의 크기와 같다면, target과 계산된 값이 일치한지를 체크하고 리턴한다. target과 일치한다면 정답에 1을 더한다. 

 

#include <string>
#include <vector>

using namespace std;

int answer = 0;
int tgt;
vector<int> nums;

void dfs(int index, int sum)
{
    if(start == nums.size())
    {
        if(sum == tgt) answer++;
        return;
    }
    dfs(start + 1, sum + nums[start]);
    dfs(start + 1, sum - nums[start]);
}

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