[Level_2] 타겟 넘버 (C++)

 

이 문제의 해설을 보기 위해 들어왔다면 dfs에 대한 알고리즘을 작성하는데에 어색함이 있는 분들이다. 

처음 문제에 접근할 때 4개 정도의 값을 받았다고 가정을 하자.  즉, numbers = {1,1,1,1}   4개의 값을 받았다고 가정을 하고 그림을 그려보자.

 

개수가 총 4개이며 사이즈는 4이다. 사이즈는 트리에서의 레벨 값이라고 생각하면 된다. 

 

그림을 한번 보자

재귀 이진 트리

 

 

즉 [인덱스 0] 은 트리에서의 [0번째 레벨] 즉, [0층] 이라는 뜻이다. 

 

각 레벨의 노드들은 자식노드 두개를 만들어내는데 그 값에서 각 레벨에 추가되는 새로운 값을 음수 그리고 양수의 값으로 변환해서 값을 더해간다.

 

 

즉, 첫 루프노드에서는 값이 정해져있지 않은데 [0 레벨]인 numbers[0] 값의 "1" 을

 

"1"x(-1) 과 "1"x(1) 

 

의 두가지 연산을 통해서 두개의 자식노드를 만들수가 있다. 

 

이러한 방식으로 재귀를 돌려가며 레벨을 한단계씩 올려주며 그 레벨값이 numbers의 사이즈와 동일하다면  더 이상 재귀를 돌릴 수 없다는 얘기다.

 

더 이상 재귀를 돌릴 수 없다면 target 변수값과 비교해서 일치한다면 카운팅을 해준다. 

 

<주석 참고>

#include <string>
#include <vector>

using namespace std;

int result; 
int com[2] = {-1, 1}; //부호 설정을 위한거야
int numbers_size;  
vector <int> v_numbers; 
int target1; 
void dfs (int sum, int level){
    if(numbers_size==level){ //현재 level이 numbers의 크기만큼 왔어?
        if(sum==target1)  // 왔으면 sum값이랑 target값이랑 비교해 
        result++;  // 이것도 같아? 그러면 result값 올려
        return; //다 확인했으니까 돌아가자
    }
    for(int i=0; i<2; i++){
        sum= sum+(com[i]*v_numbers[level]); //현재 레벨 값을 음수 양수값으로 바꾸고 sum에 저장해
        dfs(sum, level+1);  //저장한 sum값과 level을 하나 올려서 다시 dfs 돌려
        sum = sum-(com[i]*v_numbers[level]); //return 됐으니까 다른한쪽도 확인하려면 더한걸 빼줘야지
    }   
}
int solution(vector<int> numbers, int target) {
    numbers_size= numbers.size(); // level에 해당해
    target1=target;  //전역변수 target1에 저장해. 파라미터 개수 줄이기 위한거야.
    v_numbers=numbers; //전역변수 v_numbers에 numbers 저장해. 이유는 위와 같아.
    dfs(0, 0); //현재 sum값 0 , level값 0 부터 시작
    return result; //전역변수 값 반환
}