[DFS] 프로그래머스 타겟 넘버 (C++, Python 3)

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

코딩테스트 연습 - 타겟 넘버

 

문제 해결 알고리즘

 

전형적인 dfs 문제 

 

소스 코드

 

C++

#include <string>
#include <vector>

using namespace std;

int answer = 0;

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

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

 

Python 3  

global total = 0

def solution(numbers, target):
    
    answer = 0
    
    dfs(numbers, target, 0, 0)
    answer = total
    
    return answer

def dfs(v, t, s, i):
    
    if len(v) == i :
        if s == t : total = total+1
        return
    
    dfs(v, t, s+v[i], i+1);
    dfs(v, t, s-v[i], i+1);