Programmers / BFS, DFS / 타겟 넘버

< 문제링크 >

https://www.welcomekakao.com/learn/courses/30/lessons/43165

< 풀이 >

1. 주어진 숫자 배열을 DFS 기법으로 구현한다.

2. 한번은 양수로, 한번은 (-1)을 곱한 음수로 넣는다.

3. 모든 숫자를 다 설정했다면, 합계를 계산해서 target과 일치하는지 확인한다.

< 코드 >

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int answer = 0;
vector<int> num_list;

// 구성된 숫자 배열을 합산하여 target과 일치하는지 검사
int calc(int target)
{
    int total = 0;
    for (int i = 0; i < num_list.size(); i++) {
        total += num_list[i];
    }
    if (total == target) {
        return true;
    }
    return false;
}

void make_case(int n, vector<int> numbers, int target)
{
    // 모든 숫자를 다 넣었다면 계산
    if (n == numbers.size()) {
        if (calc(target)) answer++;
        return;
    }
    // 1. 해당 숫자를 양수로 넣기
    num_list.push_back(numbers[n]);
    make_case(n + 1, numbers, target);
    num_list.pop_back();
    // 2. 해당 숫자를 음수로 넣기
    num_list.push_back(-1 * numbers[n]);
    make_case(n + 1, numbers, target);
    num_list.pop_back();
    return;
}

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

< 간결한 코드 >

#include <string>
#include <vector>

using namespace std;

int total = 0;

void DFS(vector<int> numbers, int target, int sum, int n)
{
    if (n == numbers.size()) {
        if (sum == target) total++;
        return;
    }
    DFS(numbers, target, sum + numbers[n], n + 1);
    DFS(numbers, target, sum - numbers[n], n + 1);
}

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