문제

문제 접근

• 이 문제는 가볍게 보니 완전탐색 문제이다.
• target.length < 20... 그러므로, 별도의 최적화 기법은 쓰지 않아도 좋다.
• 앞에서 연산한 값이 뒤의 연산값에 영향을 미친다.
• 계산을 따라가면 일련의 트리/그래프가 나온다. 이것을 어떻게 탐색하는지에 대한 문제이다.
• 재귀를 통한 DFS나, BFS를 써서 풀 수 있지만, 나는 리스트기반 BFS로 써서 풀어보겠다.

문제 풀이

개광

• 일단, 계산이 안된 한 수인 0을 집어넣은 Array를 두자.
• 이것을 돌려가면서 배열을 계속 계산시킨다.
• 배열에 값을 넣어가며 값을 계속 갱신 시킨다.
• 그리고 마지막에, 목표값을 찾아서 return시킨다.

코드

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> numbers, int target) {
    int answer = 0;
    vector<int> rev = {0};
    for(auto i=numbers.begin();i != numbers.end(); i++)
    {
        vector<int> cal = {};
        int scal = (*i);
        for(auto a=rev.begin(); a!= rev.end() ; a++) 
        {
            int origin = (*a);
            cal.push_back(origin+scal);
            cal.push_back(origin-scal);
        }
        rev = cal;
    }

    for(auto p = rev.begin();p!=rev.end();p++)
    {
        if(target == (*p)) answer ++;
    }
    return answer;
}