타겟 넘버 43165

문제

접근 방법

BFS, DFS 둘 다 가능하다. 인덱스를 하나씩 올리며 더하거나 빼는 방식으로 합계를 저장해주면 된다. 저장된 합계가 인덱스의 끝에 와서 타겟 넘버와 같다면 정답의 개수를 증가시키면 된다.

코드

#include <vector>
#include <queue>
using namespace std;
int solution(vector<int> numbers, int target)
{
    int answer = 0;
    queue<pair<int, int>> bfs;
    bfs.push({0, 0});
    while (!bfs.empty())
    {
        auto cur = bfs.front();
        bfs.pop();
        if (cur.first == numbers.size())
        {
            if (cur.second == target)
                ++answer;
        }
        else
        {
            bfs.push({cur.first + 1, cur.second + numbers[cur.first]});
            bfs.push({cur.first + 1, cur.second - numbers[cur.first]});
        }
    }
    return answer;
}

풀이

숫자마다 더하거나 뺀다는 선택이 존재한다. 그것을 생각하며 탐색해주면 된다.