[프로그래머스 LV 2] 타겟 넘버

 

문제 설명만을 보고선 어떻게 풀어야할지 감이 잘 안왔는데 다른 사람의 풀이 중 DFS를 활용하여 풀면 된다는 문제 설명을 보고 DFS 문제 연습을 하는 겸 주석을 넣으면서 풀어 보았다.

answer은 전역 변수를 통해 함수에서 값을 추가될때마다 반영되도록 하였다.

 

지금까지 생각해봤을 때 DFS 는 재귀함수로 구현하는 데 이렇게 구현할 알고리즘을 짜는 능력이 필요하다..

#include <string>
#include <vector>

using namespace std;
int answer = 0;

 void dfs_target(vector<int> numbers, int target,int sum,int index){        //dfs=> 재귀함수로 구현, 종료조건 필요
     //종료조건
    if(index==numbers.size()){
        if(sum==target){
            answer++;
        }
        return ;
    }
    //재귀함수
     dfs_target(numbers,target,sum+numbers[index],index+1);             //양수일때
     dfs_target(numbers,target,sum-numbers[index],index+1);             //음수일때
 }

int solution(vector<int> numbers, int target) {
    
    dfs_target(numbers,target,0,0);         //시작값 index,sum 0부터
    return answer;
}