#include <string>
#include <vector>
 
using namespace std;
 
void dfs(vector<int>& vecNumber, int sum, int n, int& answer, int& iSize, int iTarget) 
{
    if (n == iSize) 
    {
        if (iTarget == sum) 
        {
            answer++;
            return;
        }
 
        else
            return;
    }
 
 	// 모든 vec의 하나하나숫자를 -와 + 두개 모두 넣어주기 
    dfs(vecNumber, sum + vecNumber[n], n + 1, answer, iSize, iTarget);
    dfs(vecNumber, sum - vecNumber[n], n + 1, answer, iSize, iTarget);
}
 
 
int solution(vector<int> numbers, int target) 
{
    int answer = 0;
    int iSize = numbers.size();
    dfs(numbers, 0, 0, answer, iSize, target);
    return answer;
}

솔직히 좀 헤맸다.

어렵지 않은 문제라 for 가지고 하려 했는데 생각보다 어려웠다.

아무리 해도 안돼서 문제 다시 봤더니 DFS, BFS... 재귀 함수로 하나하나 다 넣어주면 되는 문제... ㅎㅎ...

 

#include <string>
#include <vector>
 
using namespace std;
 
int solution(vector<int> numbers, int target) 
{
    int answer = 0;
    int size = 1 << numbers.size();
 
    for (int i = 1; i < size; i++) 
    {
        int temp = 0;
        for (int j = 0; j < numbers.size(); j++)
        {
            if (i & (1 << j)) 
                temp -= numbers[j];
 
            else 
                temp += numbers[j];
        }
        
        if (temp == target) answer++;
    }
    
    return answer;
}

이건 프로그래머스의 비트의 마법사... 보고 배우면 좋을 거 같아서 가져왔습니다.

+ Recent posts