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

문제

코드

#include <string>
#include <vector>

using namespace std;


int cnt=0;

void DFS(vector<int> &numbers, int target, int L,int sum){
    
    if(L==numbers.size()){
        if(sum==target) cnt++;
    }else{
        DFS(numbers,target,L+1,sum+numbers[L]);
        DFS(numbers,target,L+1,sum-numbers[L]);
    }
    
}

int solution(vector<int> numbers, int target) {
            
    DFS(numbers,target,0,0);
    
    return cnt;
}

풀이

정석 DFS 방법으로 풀었다.
프로그래머스는 처음사용해서 DFS 함수 인자로 입력 값을 다 넣긴 했지만...! 🙄 원래 내 방식대로라면 전역변수를 썼을 것 같다.

아무튼 DFS 함수에서 int L은 그래프의 레벨 (numbers배열의 [0][1] ...[n-1]이 순서대로 들어간다.) , int sum은 현재까지의 구한 합이다.

그래프는 L레벨에서 L+1레벨로 넘어갈 때 numbers[L] 값을 더할 것이냐 / 뺄 것이냐 두 갈래로 나뉜다.

1) 더할 때 재귀호출 DFS(numbers,target,L+1,sum+numbers[L]); 을 통해 다음 레벨로 넘어가면서 sum에 현재 레벨의 값을 더해주고

2) 뺄 때 DFS(numbers,target,L+1,sum-numbers[L]); 을 통해 다음 레벨로 넘어가면서 sum에 현재 레벨의 값을 빼준다.

numbers의 모든 값을 써야하므로 L이 numbers.size()가 되었을 때, 재귀를 멈춘다. 이때 sum값이 target값과 같으면 cnt 전역변수를 하나 더해준다.

ETC

프로그래머스 solution으로 하는 거 처음이라 완전 띠용했다.
내 맘대로 전역변수 쓰고싶은데...!!
그냥 전역 변수 만들어놓고 solution 함수 안에서 전역변수에 인풋값을 넣어도 되나보 다.
다른 사람 풀이 보니깐 그런 분들도 많은 것 같다. 🤓