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

문제 링크

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

 

 

 

풀이

문제에서 중간에 타겟넘버가 되는 경우가 없고 최종까지 가야 타겟넘버로 지정하는 것이므로 "완전탐색"이다.

재귀로 최종까지 가게되면(index값이 size랑 같을 경우) target이 같은지 여부에 따라 return 1과 0을 나누었다.

 

 

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// +, - 만 하기

// 숫자가 담긴 배열 numbers
// 타겟 넘버 target

int dbfs(vector<int> v, int i, int num, int target){
    if(i == v.size()){      // 최종 계산
        if(num == target) return 1;     // 개수 증가
        else return 0;
    }
    
    int k = i+1;
    return dbfs(v, k, num-v[i], target) + dbfs(v, k, num+v[i], target);
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    
    answer += dbfs(numbers, 0, 0, target);       // 개수
    
    return answer;      // 타겟 넘버를 만드는 방법의 수를 리턴
}