프로그래머스 | 타겟넘버

dfs돌면서

0부터 시작, numbers[i] 값을 더하거나 빼기

n <= dfs 돌면서 더하거나 뺀 값 저장하는 변수

dfs(++), dfs(--)돌기

끝까지 돈 상태 + target 성공시 ans ++하고 리턴!

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

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

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

생각보다 너무 쉽게 성공하긴 했는데

이게 numbers길이가 20일 경우에는

dfs를 2^20번을 돌아야되는건데

너무 많이 도는거같아서 중간에 탈출 조건이 필요할듯 함.

#include <string>
#include <vector>
#include <numeric>
#include <cmath>
using namespace std;

void dfs(vector<int> numbers, int idx, int target, int n, int &ans, int sum){
    if(idx == numbers.size()){
        if(n == target) ans++; 
        return;
    }
    
    for(int i = -1; i<=1; i+=2){
        if (abs(target - n) > sum) return; //여기 중간에 계산 안될거같은거 탈출 조건 추가
        dfs(numbers, idx+1, target, n+(numbers[idx]*i), ans, sum-numbers[idx]);
    }
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    int sum = accumulate(numbers.begin(), numbers.end(), 0);
    dfs(numbers, 0, target, 0, answer, sum);
    return answer;
}

확실히 조건을 넣으니까

조금 더 빨라졌다

---

 

전에 bitset공부할 때 이걸로 조합을 풀 수도 있다고 했는데 그것도 한번 써볼까

#include <string>
#include <vector>
#include <bitset>
using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    int size = 1 << numbers.size(); // 2의 numbers.size()제곱 만큼의 길이 필요

    for(int i = 0; i<size; ++i){
        bitset<20>comb = i;
        int n = 0;
        for(int b = 0; b<numbers.size(); ++b){
            comb[b]? n+=numbers[b] : n-=numbers[b];
        }
        if(n == target) answer++;
    }
    return answer;
}

확실히 이렇게 하니까 시간이 덜 걸린다

함수 호출하는 시간이 줄어들어서 그런가...

앞에가 dfs함수 호출한거, 뒤에가 bitset을 활용한거

비교 항목	DFS (재귀 탐색)	Bitmask (반복문)
시간 복잡도	O(2^N)	O(2^N)
작은 입력 (N ≤ 15)	빠르거나 비슷 (오버헤드 미미)	비슷
큰 입력 (N ≥ 20)	느려짐 (재귀 호출 부담↑)	더 빠름
조건 분기 (Pruning)	가능 → 탐색 수를 줄임	불가능
가독성	직관적, 설계 쉬움	조금 난해