타겟 넘버 (feat. 프로그래머스, 43165번)

타겟 넘버
https://programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

반응형

// woohyeon.kim
#include <string>
#include <vector>

using namespace std;

int answer;
void dfs(const vector<int>& numbers, const int& target, int index, int sum, bool sign)
{
    if(sign)
        sum += numbers[index++];
    else
        sum -= numbers[index++];
    if(numbers.size() != index)
    {
        dfs(numbers, target, index, sum, true);
        dfs(numbers, target, index, sum, false);
    }
    else
    {
        if(sum == target)
            ++answer;
    }
}

int solution(vector<int> numbers, int target) {
    answer = 0;
    int sum = 0;
    dfs(numbers, target, 0, sum, true);
    dfs(numbers, target, 0, sum, false);
    return answer;
}
// *&)*@*

그래프를 모두 탐색하여 연산했을 경우의 결과가 예상한 target과 같은지를 보면 됩니다.

다만 그래프가 처음부터 주어진 것이 아니라, +와 - 각각을 만들어야 한다는 차이만 있을 뿐입니다.