Level 2. 타겟 넘버

Level 2. 타겟 넘버

 

 

next_permutation() 함수를 이용해 [-1, -1, ..., -1, -1], [-1, -1, ..., -1, 1]부터 [-1, 1, ..., 1, 1], [1, 1, ..., 1, 1]까지의 각 부호 배열의 조합을 모두 계산했다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> numbers, int target)
{
    size_t size = numbers.size();
    vector<int> sign(size, -1);
    int answer = 0, i = size - 1;

    while (true)
    {
        vector<int> t_sign = sign;

        do
        {
            int sum = 0;

            for (int j = 0; j < size; ++j)
                sum += numbers[j] * t_sign[j];

            if (sum == target)
                ++answer;
        }
        while (next_permutation(t_sign.begin(), t_sign.end()));

        if (0 <= i)
            sign[i--] = 1;
        else
            break;
    }

    return answer;
}

 

이 풀이를 보고 자괴감이 들었다.. DFS 다시 공부해야 하나..

 

분명 공부했는데 써먹질 못하고 있다..

 

#include <iostream>
#include <vector>

using namespace std;

int rDFS(vector<int>& numbers, int target, int sum, int n)
{
    if (numbers.size() <= n)
        return (sum == target);

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

int solution(vector<int> numbers, int target)
{
    return rDFS(numbers, target, 0, 0);
}