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

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

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

---

 문제 풀이

따로 벡터를 선언해서 거기에 연산자를 넣어 DFS를 구현한 문제이다!

 느낀 점

어렵지는 않았다. 근데 다른 분의 코드(코드2)를 참고해보니 내 코드가 너무나도 직관적으로 구현한 코드 같다. 다음엔 조금 더 응용을 해봐야겠다.

 코드1

#include <string>
#include <vector>

using namespace std;

vector<char> oper;
int answer;

void DFS(int cnt, vector<char> oper, vector<int> numbers, int target) {
    if (cnt == numbers.size()) {
        int result = 0;
        for (int i = 0; i < numbers.size(); i++) {
            if (oper[i] == '+') result += numbers[i];
            else result -= numbers[i];
        }
        if (result == target) answer++;
        return;
    }
    else {
        for (int i = 0; i < 2;i++) {
            oper.push_back("+-"[i]);
            DFS(cnt + 1, oper, numbers, target);
            oper.pop_back();
        }
    }
}

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

 코드2

#include <string>
#include <vector>

using namespace std;

int total;

void DFS(vector<int> &numbers, int &target,int sum,int n) {
    if(n >= numbers.size()){
        if(sum == target) total++;
        return;
    }

    DFS(numbers, target, sum + numbers[n], n+1);
    DFS(numbers, target, sum - numbers[n], n+1);
}

int solution(vector<int> numbers, int target) {
    int answer = 0;

    DFS(numbers, target, numbers[0] , 1);
    DFS(numbers, target, -numbers[0], 1);

    answer = total;

    return answer;
}