프로그래머스 타겟넘버 문제 ( DFS 알고리즘)

 

문제

 

#include <string>
#include <vector>

using namespace std;

void DFS(vector<int>& _Numbers, int _Target, int _Sum, int _iCount, int* _iResult)    
{
    
    if(_iCount == _Numbers.size())
    {
        if(_Sum == _Target)
        { 
            (*_iResult)++;             
        }
        return; 
    }
    
    int Sum_1 = _Sum +_Numbers[_iCount];
    int Sum_2 = _Sum -_Numbers[_iCount];

    DFS(_Numbers, _Target, Sum_1, _iCount+1, _iResult); 
    DFS(_Numbers, _Target, Sum_2, _iCount+1, _iResult); 
    
}


int solution(vector<int> numbers, int target) 
{

    int answer = 0;
    
    DFS(numbers, target, 0, 0, &answer);    
    
    return answer;
}

 

 

문제 접근 순서

 

1. 해당 문제를 처음 본 순간 각각의 경우의 수를 모두 생각해야 한다는 사고를 함.

 

2. 원래의 결과에서 다시 덧셈 , 뺄셈을 진행해야하고 모든 숫자를 다 사용해야 하므로 DFS 알고리즘이 생각났다. 

-> 즉 트리와 같이 내려가면서 계속적으로 모든 결과 값을 저장하면서 연산을 진행해야 했음. 

 

3. 재귀 함수를 통한 DFS 구현 

 

4. 결과값은 pointer를 통해 메모리 공유를 하여 구현함.