프로그래머스 타겟넘버 C++

문제

bfs로 풀어야겠다고 생각했다. 또, 모든 경우를 탐색해야하기 때문에 방문 여부는 기록할 필요가 없다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

/*
1. 큐에서 숫자들을 빼서 그 다음 올 숫자를 +, - 시켜준다음에 다시 큐에 넣어준다
-> 언제까지? 큐가 빌 때까지
-> 이걸 몇번? 모든 숫자에 대해서
*/

int solution(vector<int> numbers, int target) {
    int answer = 0;
    int cnt=0;
    queue<int> q;
    while (cnt<numbers.size()){
        queue<int> tmp;
        if (cnt==0){
            q.push(0);
        }
        while (!q.empty()){
            int x = q.front();
            q.pop();
            tmp.push(x+numbers[cnt]);
            tmp.push(x-numbers[cnt]);
        }
        q=tmp;
        while (!tmp.empty()){ // 임시 큐 비워주기
            tmp.pop();
        }
        cnt++;
    }
    while (!q.empty()){
        int x = q.front();
        if (x==target){
            answer++;
        }
        q.pop();
    }
    return answer;
}

큐에서 숫자들을 빼서 그 다음에 올 숫자들을 + , - 시켜준 다음에 큐에 넣주면 된다.

매번 큐가 빌 때까지 반복을 해야하기 때문에 큐와 임시 큐를 선언해준다. 그리고 이 작업을 number에 저장된 모든 숫자에 대해서 수행하면 쉽게 풀 수 있다.