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

문제

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

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

문제풀이

DFS를 이용하여 모든 경우의 수를 탐색한다.

num이 끝 수이면 더 이상 할 연산이 없으므로 목푯값인 target과 같은지를 확인하고, 같다면 answer의 개수를 1 늘린다.

num이 끝 수가 아닐 때 다음 숫자를 +하는 경우의 수, 다음 숫자를 -하는 경우의 수를 확인한다.

 

코드

#include <string>
#include <vector>

using namespace std;

vector<int>number;
int answer, target_num;

void DFS(int idx, int sum) {
    if (idx == number.size()) {
        if (sum == target_num) ++answer;
        return;
    }

    DFS(idx + 1, sum - number[idx]);
    DFS(idx + 1, sum + number[idx]);
}

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