[Lv 2] 타겟 넘버

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

프로그래머스

 

이 문제는 dfs를 통해 해결할 수 있다.

문제에서 numbers 배열을 순서대로 사용하고, 부호를 바꿔 조합을 하여 target값이 나오는 경우의 수를 구하라고 하였다.

이 조건대로 수를 나열하면 그래프의 형태로 이루어지는 것을 알 수 있다.

따라서 dfs를 사용해 값을 누적하여 target값이 나오면 answer를 증가시키면 된다.

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int answer = 0;

void dfs(int n, int idx, vector<int> numbers, int target){
    if(idx >= numbers.size()) {
        if(n == target){
            answer++;
        }
        return;
    }
    dfs(n + (-1 * numbers[idx]), idx + 1, numbers, target);
    dfs(n + numbers[idx], idx + 1, numbers, target);
}

int solution(vector<int> numbers, int target) {
    answer = 0;
    
    // -1 1
    dfs(-1 * numbers[0], 1, numbers, target);
    dfs(numbers[0], 1, numbers, target);
    // -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+1 1+1+1 1-1+1
    return answer;
}