프로그래머스 - 타겟넘버

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

접근

가능한 모든 경우의 수를 탐색하는 dfs 문제입니다.

numbers의 길이가 최대 20이므로 dfs의 깊이는 최대 20이며 트리로 보았을 때 리프노드의 최대 개수는 2^20 = 약 100만 입니다.

끝까지 연산을 해보아야 되는 문제 같아서 백트랙킹 방식으로 가지치기는 하지 않았습니다.

이런 문제를 풀 때 괜히 모든걸 구현할 필요는 없고, 그때 그때 합이 얼마인지만 알면 됩니다.

예전에 비슷한 문제에서 괜히 연산자 조합을 따졌다가 고생한 경험이 있어서 손쉽게 해결할 수 있었습니다.

다음은 코드 전문입니다.

#include <string>
#include <vector>

using namespace std;

void dfs(int depth,int tot);

vector<int> nums;
int t,co;
int solution(vector<int> numbers, int target) {
    int answer = 0;
    nums = numbers;
    t = target;
    co = 0;
    dfs(0, 0);
    answer = co;
    return answer;
}
void dfs(int depth,int tot){
    if (depth == int(nums.size())) {
        if (tot == t) {
            co++;
        }
        return;
    }
    else{
        dfs(depth+1, tot+nums[depth]);
        
        dfs(depth+1, tot-nums[depth]);
        
    }
    
}