Programmers[level 2] 타겟넘버

타겟넘버

• 문제 설명
  

• 제한 사항
  

• 입출력 예
  

• 문제 풀이

문제를 간단히 하여 numbers = [1, 1], targer = 0 이라고 가정한다면 가능한 쌍은 아래와 같다.
<1단계>
+1 //
-1 //
<2단계> (1단계 후 원소가 하나 남았기 때문에 재귀는 계속 돌아감)
+1+1
+1-1 //
-1+1
-1-1 //
이제 count = 2, 우리에게 주어진 numbers의 원소도 2개니깐 끝.
나온 4가지의 경우 중에서 target = 0인 값이 몇개인지 확인 후 answer에 추가(answer++)

만약, numbers = [1, 1, 1], targer = 0 이라고 가정한다면, 가능한 쌍은 아래와 같다.
<1단계>
+1 //
-1 //
<2단계> (원소가 2개 남았기 때문에 재귀는 계속 돌아감)
+1+1
+1-1 //
-1+1
-1-1 //
<3단계> (원소가 1개 남았기 때문에 재귀는 계속 돌아감)
+1+1+1
+1+1-1
-1+1+1
-1+1-1 //
+1-1+1
+1-1-1
-1-1+1
-1-1-1

즉, 매 깊이(count)마다 2배씩 늘어난다.
count = 1, 경우의 수 = 2
count = 2, 경우의 수 = 22
count = 3, 경우의 수 = 22*2
...
count = 10, 경우의 수 = 2^10

코드

#include <vector>
using namespace std;
// 깊이 우선 탐색 DFS

// 벡터, 정답횟수, 찾아야 하는 숫자, 들어간 깊이, 현재까지 합
void dfs(vector<int>& numbers, int& answer, int target, int count = 0, int sum = 0){
    // 마지막까지 순회했다면 (모든 숫자를 이용했을 때 재귀를 종료)
    if (count == numbers.size()-1) {
        //지금까지 더한값에 마지막 원소를 더할때 타겟과 같다면 카운트 증가
        if (target == sum + numbers[count]) answer++;
        //지금까지 더한값에 마지막 원소를 뺄때 타겟과 같다면 카운트 증가
        if (target == sum - numbers[count]) answer++;
        return;
    }
    // 최대깊이까지 가지않았다면 더하거나 뺀상태로 탐색
    dfs(numbers, answer, target, count+1, sum+numbers[count]);
    dfs(numbers, answer, target, count+1, sum-numbers[count]);
}
 
int solution(vector<int> numbers, int target) {
    int answer = 0;
    dfs(numbers, answer, target, 0, 0);
    return answer;
}