[알고리즘C++]타겟 넘버

오늘의 문제

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

타겟 넘버

나의 풀이

#include <string>
#include <vector>
#include <iostream>

using namespace std;

string per;        
int count=0;
int accept;
int sum=0;
bool check[21] = { false, }; 

void permutation(vector<int>num, int depth, int n, int result, int idx){  
    if(result - (sum-result) > accept)
        return;
    if(depth == n){
        if(result - (sum-result) == accept)
            count++;
        return;
    }
    for(int i = idx; i < num.size(); i++){
        if(!check[i]){
            check[i] = true;        
            permutation(num, depth + 1, n, result + num[i], i+1);  
            check[i] = false;      
        }
    }
}

int solution(vector<int> numbers, int target) {
    accept = target;
    for(int i=0;i<numbers.size();i++) sum += numbers[i];
    for(int i=1;i<numbers.size();i++){
        permutation(numbers, 0, i, 0, 0);
        
    }
    return count;
}

모범 답안

#include <string>
#include <vector>

using namespace std;

int total;

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, numbers[0] , 1);
    DFS(numbers, target, -numbers[0], 1);

    answer = total;

    return answer;
}

배울 점

• 이런식으로 재귀를 쓰면 되는데 아직 이해도가 높지 않아 바로 응용이 어렵다. 연습 필요