프로그래머스 레벨2 <타겟 넘버> C++ 풀이

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

프로그래머스

 

어렵지 않은 DFS 문제였습니다.

 

주어진 vector의 현재 위치의 값을 더하는경우와 빼는경우를 체크해서 모든 경우를 탐색해보고 마지막 인덱스까지 갔을때, 그 값이 문제에서 주어진 타겟과 같으면 경우의 수를 하나 늘려주면 간단하게 답을 구할 수 있었습니다.

 

 

#include <string>
#include <vector>
 
using namespace std;
 
int last;
int goal;
int answer = 0;
 
void calcul(int val,int curIdx,vector<int>& numbers)
{
    if (curIdx >= last)
    {
        if (val == goal)
        {
            answer++;
            return;
        }            
        else
            return;
    }
    else
    {
        calcul(val+numbers[curIdx+1],curIdx+1,numbers);
        calcul(val-numbers[curIdx+1],curIdx+1,numbers);
    }
}
 
int solution(vector<int> numbers, int target) {
    
    int size = numbers.size();
    last = size-1;
    goal = target;
    
    calcul(0+numbers[0],0,numbers);
    calcul(0-numbers[0],0,numbers);
    
    return answer;
}