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

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

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

코드 설명

연산 (-,+)을 branch로 생각하여 DFS를 구성하였다.

처음 main문에서 넘겨주는 값을 number[level]로 했다가 바닥조건에서 이를 고려안해서 실수했다....

프로그래머스 환경에서 dfs 디버깅은 좀 쉽지 않은것 같다...

 

코드

#include <string>
#include <vector>

using namespace std;
int arr[2]={-1,1};
int answer=0;
void dfs(int level,int now,vector<int>&numbers,int target){
    if(level==numbers.size()){
        if(now==target) answer++;
        return;
    }
    for(int i=0;i<2;i++){
        int sum=numbers[level]*arr[i];
        now+=sum;
    
        dfs(level+1,now,numbers, target);
        now-=sum;
        
    }
    
}
int solution(vector<int> numbers, int target) {
    
    
    int n=numbers.size();
    dfs(0,0,numbers,target);
    
    return answer;
}